一、使用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; } }