c++++中利用指针进行数组去重的核心在于通过双指针实现原地修改和高效遍历。1. 使用 slow 和 fast 两个指针，slow 指向去重后的末尾，fast 遍历数组；2. 当 fast 指向的元素与 slow 不同时，将其复制到 slow+1 的位置并移动 slow；3. 对于未排序数组，可先排序再用双指针，或使用哈希表记录已出现元素以实现 o(n) 时间复杂度；4. 可借助 std::unique 和 std::erase 实现简洁但效率较低的去重方法；5. 对象或结构体数组需重载 == 运算符或提供自定义比较函数；6. 原地操作虽节省内存但会修改原始数组，必要时应创建副本或采用替代方案如哈希表、外部排序。
C++中利用指针进行数组去重的核心在于，通过指针操作实现高效的遍历和原地修改，避免额外的内存开销。双指针算法是关键，一个指针用于遍历数组，另一个指针指向去重后的数组的末尾。
解决方案
核心思路是使用两个指针：
slow
和
fast
。
fast
指针遍历整个数组，
slow
指针指向去重后数组的末尾。如果
fast
指针指向的元素与
slow
指针指向的元素不同，则将
fast
指针指向的元素复制到
slow + 1
的位置，并将
slow
指针向后移动一位。
立即学习“C++免费学习笔记（深入）”；
以下是一个示例代码：
#include #include int* removeDuplicates(int* arr, int size) { if (size == 0) { return arr; // 空数组，无需去重 } int* slow = arr; int* fast = arr + 1; while (fast < arr + size) { if (*fast != *slow) { *(++slow) = *fast; // 先移动 slow 指针，再赋值 } ++fast; } return arr; // 返回原始数组的指针，但数组已被修改}int main() { int arr[] = {1, 1, 2, 2, 3, 4, 4, 5}; int size = sizeof(arr) / sizeof(arr[0]); removeDuplicates(arr, size); // 输出去重后的数组（实际长度需要单独计算） for (int i = 0; i < size; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; // 计算去重后的数组的实际长度 int* last = arr; while(*(last+1) != 5 && last < arr + size - 1){ last++; } std::cout << "去重后的数组长度: " << last - arr + 1 << std::endl; return 0;}
这段代码直接修改了原始数组。注意，虽然数组的内容被修改了，但数组的大小并没有改变。你需要单独记录去重后数组的实际长度，例如通过计算
slow
指针指向的最后一个有效元素的索引。
如何处理未排序的数组去重？
如果数组未排序，一种方法是先对其进行排序，然后再使用双指针算法。排序可以使用
std::sort
函数。但是，排序的时间复杂度为 O(n log n)，所以对于未排序数组，如果对性能要求较高，可以考虑使用哈希表（
std::unordered_set
）来记录已经出现的元素，这样可以在 O(n) 的时间复杂度内完成去重，但会占用额外的内存空间。 例如：
#include #include #include int removeDuplicatesUnsorted(int* arr, int size) { if (size == 0) { return 0; } std::unordered_set seen; int j = 0; for (int i = 0; i < size; ++i) { if (seen.find(arr[i]) == seen.end()) { seen.insert(arr[i]); arr[j++] = arr[i]; } } return j; // 返回去重后的数组长度}int main() { int arr[] = {5, 2, 1, 2, 3, 4, 1, 5}; int size = sizeof(arr) / sizeof(arr[0]); int newSize = removeDuplicatesUnsorted(arr, size); // 输出去重后的数组 for (int i = 0; i < newSize; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; std::cout << "去重后的数组长度: " << newSize << std::endl; return 0;}
使用
std::unique
std::unique
和
std::erase
进行去重的优缺点？
C++ 标准库提供了
std::unique
函数，它可以将数组中相邻的重复元素移动到数组的末尾，并返回指向去重后数组末尾的迭代器。然后，可以使用
std::erase
函数删除这些重复元素。这种方法的优点是简洁易懂，缺点是效率相对较低，因为它需要移动元素和删除元素。
#include #include #include int main() { std::vector arr = {1, 1, 2, 2, 3, 4, 4, 5}; // 使用 std::unique 将重复元素移动到末尾 auto it = std::unique(arr.begin(), arr.end()); // 使用 std::erase 删除重复元素 arr.erase(it, arr.end()); // 输出去重后的数组 for (int i = 0; i < arr.size(); ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; std::cout << "去重后的数组长度: " << arr.size() << std::endl; return 0;}
std::unique
只能作用于连续内存空间，例如
std::vector
。 对于原始数组，需要先将其复制到
std::vector
中。
如何处理包含对象或结构体的数组去重？
如果数组包含的是对象或结构体，你需要定义一个比较函数，用于判断两个对象是否相等。然后，可以将这个比较函数传递给
std::unique
函数。或者，重载
==
运算符。
例如：
#include #include #include struct Point { int x; int y; bool operator==(const Point& other) const { return x == other.x && y == other.y; }};int main() { std::vector arr = {{1, 2}, {1, 2}, {3, 4}, {5, 6}, {5, 6}}; auto it = std::unique(arr.begin(), arr.end()); arr.erase(it, arr.end()); for (const auto& p : arr) { std::cout << "(" << p.x << ", " << p.y << ") "; } std::cout << std::endl; std::cout << "去重后的数组长度: " << arr.size() << std::endl; return 0;}
如果对象或结构体没有重载
==
运算符，则需要提供一个自定义的比较函数，并将其传递给
std::unique
。
#include #include #include struct Point { int x; int y;};bool comparePoints(const Point& a, const Point& b) { return a.x == b.x && a.y == b.y;}int main() { std::vector arr = {{1, 2}, {1, 2}, {3, 4}, {5, 6}, {5, 6}}; auto it = std::unique(arr.begin(), arr.end(), comparePoints); arr.erase(it, arr.end()); for (const auto& p : arr) { std::cout << "(" << p.x << ", " << p.y << ") "; } std::cout << std::endl; std::cout << "去重后的数组长度: " << arr.size() << std::endl; return 0;}
原地操作的局限性与替代方案
原地操作虽然节省了内存，但它直接修改了原始数组，这在某些情况下可能不合适。如果需要保留原始数组，可以先创建一个副本，然后在副本上进行去重操作。此外，如果数组非常大，原地操作可能会导致性能问题，因为需要频繁地移动元素。在这种情况下，可以考虑使用其他算法，例如哈希表，或者使用外部排序。
以上就是C++中如何用指针实现数组去重 双指针算法与原地操作技巧的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1471717.html
微信扫一扫 
支付宝扫一扫 
