您的位置:

C++如何去除数组中重复元素

一、使用STL中的set容器

set是一个有序且不能重复的容器,C++中STL提供了set容器可以快速去重。通过set容器可将元素插入到set中,但不会重复,同时可以使用unique()函数将重复元素排到后面,然后通过erase()函数将重复元素删除。

#include <set>
#include <algorithm>
#include <vector>

using namespace std;

void removeDuplicates(int arr[], int n){
    set<int> s;

    for (int i = 0; i < n; i++){
        s.insert(arr[i]);
    }

    copy(s.begin(), s.end(), arr);
    int newSize = s.size();
    for (int i = newSize; i < n; i++){
        arr[i] = 0;
    }
}

二、使用C++11中的unique函数

C++11中的unique函数可以在数组中移除相邻的重复元素,但不会真正地删除元素。可以结合erase函数删除后面的重复元素。unique函数需要注意的是,传入的数组必须是有序的。为了在不使用sort函数的情况下实现有序的数组,可以使用algorithm头文件中的sort函数。

#include <algorithm>

using namespace std;

void removeDuplicates(int arr[], int n){
    sort(arr, arr + n);
    int newSize = unique(arr, arr + n) - arr;
    for (int i = newSize; i < n; i++){
        arr[i] = 0;
    }
}

三、使用双重循环

双重循环是一种朴素的方法。先用第一个循环遍历每一个元素,然后用第二个循环遍历每一个和该元素进行比较,如果找到相同的元素,则将其后面所有元素向前移动,最后将新的数组长度减去重复元素的个数。

void removeDuplicates(int arr[], int n){
    int newSize = n;
    for (int i = 0; i < newSize; i++){
        for (int j = i + 1; j < newSize; j++){
            if (arr[i] == arr[j]){
                for (int k = j; k < newSize; k++){
                    arr[k] = arr[k + 1];
                }
                newSize--;
                j--;
            }
        }
    }

    for (int i = newSize; i < n; i++){
        arr[i] = 0;
    }
}