C++中如何用指针实现数组去重双指针算法与原地操作技巧-C++-PHP中文网

C++中如何用指针实现数组去重双指针算法与原地操作技巧

P粉602998670

发布： 2025-08-18 11:49:01

原创

919人浏览过

c++++中利用指针进行数组去重的核心在于通过双指针实现原地修改和高效遍历。1. 使用 slow 和 fast 两个指针，slow 指向去重后的末尾，fast 遍历数组；2. 当 fast 指向的元素与 slow 不同时，将其复制到 slow+1 的位置并移动 slow；3. 对于未排序数组，可先排序再用双指针，或使用哈希表记录已出现元素以实现 o(n) 时间复杂度；4. 可借助 std::unique 和 std::erase 实现简洁但效率较低的去重方法；5. 对象或结构体数组需重载 == 运算符或提供自定义比较函数；6. 原地操作虽节省内存但会修改原始数组，必要时应创建副本或采用替代方案如哈希表、外部排序。

C++中如何用指针实现数组去重双指针算法与原地操作技巧

C++中利用指针进行数组去重的核心在于，通过指针操作实现高效的遍历和原地修改，避免额外的内存开销。双指针算法是关键，一个指针用于遍历数组，另一个指针指向去重后的数组的末尾。

解决方案

核心思路是使用两个指针：

slow

登录后复制

和

fast

登录后复制

。

fast

登录后复制

指针遍历整个数组，

slow

登录后复制

指针指向去重后数组的末尾。如果

fast

登录后复制

指针指向的元素与

slow

登录后复制

指针指向的元素不同，则将

fast

登录后复制

指针指向的元素复制到

slow + 1

登录后复制

的位置，并将

slow

登录后复制

指针向后移动一位。

立即学习“C++免费学习笔记（深入）”；

以下是一个示例代码：

#include <iostream>
#include <algorithm>

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) 的时间复杂度内完成去重，但会占用额外的内存空间。例如：

人声去除

用强大的AI算法将声音从音乐中分离出来

查看详情

#include <iostream>
#include <algorithm>
#include <unordered_set>

int removeDuplicatesUnsorted(int* arr, int size) {
    if (size == 0) {
        return 0;
    }

    std::unordered_set<int> 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::erase

登录后复制

进行去重的优缺点？

C++ 标准库提供了

std::unique

登录后复制

函数，它可以将数组中相邻的重复元素移动到数组的末尾，并返回指向去重后数组末尾的迭代器。然后，可以使用

std::erase

登录后复制

函数删除这些重复元素。这种方法的优点是简洁易懂，缺点是效率相对较低，因为它需要移动元素和删除元素。

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> 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 <iostream>
#include <algorithm>
#include <vector>

struct Point {
    int x;
    int y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

int main() {
    std::vector<Point> 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 <iostream>
#include <algorithm>
#include <vector>

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<Point> 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;
}

登录后复制