详解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
       
        
使用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
             

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


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

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

              
#include
#include
                
using namespace std;
void removeDuplicate(vector
                 & vec){
    for(int i=0; i
                   vec{1,2,2,3,3,3,4,5};
    removeDuplicate(vec);
    for(int i=0; i
                   

                    
使用自定义函数实现去重能够灵活地处理各种需求，但是时间复杂度比较高，需要用两个循环遍历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
                         

                          
使用双指针方法实现去重是一种高效的方法，但是需要注意的是，这个方法只能适用于已经排好序的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
                              
                              
使用unordered_map方法能快速地实现vector容器的去重，使用起来也比较方便。但是unordered_map容器提高了空间复杂度，需要根据实际情况选择使用。