C++ 的多种去重方法

vector 利用 set

第一种方法是简单的利用 set 的特性，这部分代码比较简单

代码如下：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
    int myints[] = {1, 2, 3, 1, 1};
    int len = sizeof(myints) / sizeof(int);
    vector<int> vec(myints, myints + len);
    //将普通数组转换为 vector
    set<int> s(vec.begin(), vec.end());
    //将 vector 转换为 set，set 数据结构自动去重
    vec.assign(s.begin(), s.end());
    //再将 set 转换为 vector 进行使用
    for (auto &x : vec) cout << x << " ";
    return 0;
}

结合 sort 和 unique 函数

unique() 函数将相邻且重复的元素删除，然后空出的位置用他后面的元素一次向前移动覆盖
然后返回边界元素的迭代器，供 erase 等类似函数调用
再用 erase 函数隐藏掉从这个元素到最后元素的所有的元素。（只改变 size 不改变 capacity ）

所以想要去重的话，可以先进行排序，这样重复元素就会堆一起了，调用 unique() 函数，再调用 erase 函数隐藏重复元素。

代码如下:

#include <algorithm>  // algorithm 库包含了 sort 和 unique 函数
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int myints[] = {1, 2, 3, 1, 1};
    int len = sizeof(myints) / sizeof(int);
    vector<int> vec(myints, myints + len);
    // 将已有的数组转换为 vector 方便调用各种函数接口
    sort(vec.begin(), vec.end());
    // 对 vector 进行排序 1 1 1 2 3
    auto ret = unique(vec.begin(), vec.end());
    // 将 vector 进行去重的操作，将所有元素的个数限制到最大一个，
    // 后面的元素依次向前移动, 后面元素移动之前的位置对应的值，仍然不变
    // 1 2 3 2 3
    // 同 后面的 remove 函数，ret 指向的是相关的边界，可以供 erase 函数使用
    // 排列完成后调用 earse 和 unique 接口，两个函数的参数都是 begin 和 end
    vec.erase(ret, vec.end());
    // vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (auto &i : vec) cout << i << " ";
    // 1 2 3
    for (int i = 0; i < vec.capacity(); i++) cout << vec[i] << " ";
    // 1 2 3 2 3
    return 0;
}

C++ 自带的 remove 函数:

同 unique 函数的返回值
目的是删除 vector 中等于目标值的所有元素

代码如下：

#include <algorithm> // algorithm 函数包含了 remove 函数
#include <iostream>
#include <vector>
using namespace std;
int main() {
    std::vector<int> vec(0);
    for (int i = 0; i < 10; i++) {
        vec.push_back(i + 1);
    }
    vec[1] = 7, vec[0] = 7, vec[2] = 7;
    vec.push_back(-1);
    // vector: 7 7 7 4 5 6 7 8 9 10 -1
    auto ret = std::remove(vec.begin(), vec.end(), 7);
    cout << *ret << endl;
    // *ret == 8 
    // vector: 4 5 6 8 9 10 -1 8 9 10 -1
    // 可见 remove 的作用就是将所有等于目标值的函数删除，
    // 然后后面的元素一次向前移动，
    // 但是向前移动之后，之前在后面的元素的值仍然不变
    vec.erase(ret, vec.end());
    // 4 5 6 8 9 10 -1
    // 使用 remove 函数获取删除目标值之后的边界下标
    // 然后使用 erase 函数将边界之后的元素进行 空间隐藏
    for (auto &i : vec) {
        std::cout << i << " ";
    }
    // 4 5 6 8 9 10 -1
    for (int i = 0; i < 10; i++) {
        cout << vec[i] << " ";
    }
    // 4 5 6 8 9 10 -1 8 9 10 
    // (仍然存在其余元素， erase 只做了空间隐藏)
    // erase 将 vector 的 size 进行相应的缩小， 但是 capacity 仍然不变
    return 0;
}

双指针手写 unique

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size(); 
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                nums[k] = nums[i]; 
                k++; 
            }
        }
        return k; 
    }
};