詳解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容器提高了空間複雜度，需要根據實際情況選擇使用。