详解vector去重方法

一、使用set去重

使用set去重是一种非常方便的方法。因为set容器中不允许有重复元素存在，因此我们可以将vector中的元素放到set中，再将set中的元素重新放回vector中，实现去重效果。

#include
#include
#include
using namespace std;
int main(){
    vector vec{1,2,2,3,3,3,4,5};
    set s(vec.begin(), vec.end());
    vec.assign(s.begin(), s.end());
    for(int i=0; i<vec.size(); i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}

使用set去重方法简单易懂，但是需要注意的是，set中的元素是自动按升序排序的。如果需要按照一定规则排序，需要重载比较运算符。

二、使用unique去重

unique函数可以消除相邻重复元素，但是它不能处理vector容器中所有重复的元素，需要结合erase函数才能去重。

#include
#include
#include
using namespace std;
int main(){
    vector vec{1,2,2,3,3,3,4,5};
    auto end_unique = unique(vec.begin(), vec.end());
    vec.erase(end_unique, vec.end());
    for(int i=0; i<vec.size(); i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}

使用unique去重需要注意的是，输入的vector中的元素必须是已经排过序的，否则结果不准确。

三、使用自定义函数实现去重

使用自定义函数实现去重是一种非常灵活的方法。这个方法的本质是通过循环遍历vector容器，将其中重复的元素进行删除。

#include
#include
using namespace std;
void removeDuplicate(vector& vec){
    for(int i=0; i<vec.size(); i++){
        for(int j=i+1; j<vec.size(); j++){
            if(vec[i] == vec[j]){
                vec.erase(vec.begin() + j);
                j--;
            }
        }
    }
}
int main(){
    vector vec{1,2,2,3,3,3,4,5};
    removeDuplicate(vec);
    for(int i=0; i<vec.size(); i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}

使用自定义函数实现去重能够灵活地处理各种需求，但是时间复杂度比较高，需要用两个循环遍历vector容器。

四、使用双指针方法实现去重

双指针方法是一种高效的去重方法，它将vector容器看做一个已经排好序的数组，使用两个指针维护vector容器中唯一元素的个数。这个方法的时间复杂度为O(n)，由于是双指针操作，因此空间复杂度比较低。

#include
#include
using namespace std;
void removeDuplicate(vector& vec){
    if(vec.empty()) return;
    int slow=0, fast=1;
    while(fast < vec.size()){
        if(vec[fast] != vec[slow]){
            vec[++slow] = vec[fast];
        }
        fast++;
    }
    vec.resize(slow+1);
}
int main(){
    vector vec{1,2,2,3,3,3,4,5};
    removeDuplicate(vec);
    for(int i=0; i<vec.size(); i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}

使用双指针方法实现去重是一种高效的方法，但是需要注意的是，这个方法只能适用于已经排好序的vector容器。

五、使用unordered_map实现去重

使用unordered_map可以实现在O(n)的时间复杂度下实现vector容器的去重效果。这个方法通过unordered_map容器自动排除重复元素的思想来实现。

#include
#include
#include
using namespace std;
void removeDuplicate(vector& vec){
    unordered_map unmap;
    for(auto it=vec.begin(); it != vec.end(); ){
        if(unmap[*it] == true){
            it = vec.erase(it);
        }else{
            unmap[*it] = true;
            ++it;
        }
    }
}
int main(){
    vector vec{1,2,2,3,3,3,4,5};
    removeDuplicate(vec);
    for(int i=0; i<vec.size(); i++){
        cout<<vec[i]<<" ";
    }
    return 0;
}

使用unordered_map方法能快速地实现vector容器的去重，使用起来也比较方便。但是unordered_map容器提高了空间复杂度，需要根据实际情况选择使用。