C++数组去重方法
在C++中，数组去重是一个常见的操作，以下是一些常见的数组去重方法：
一、使用std::sort和std::unique（STL方法）
-
原理
-
首先，std::sort函数用于对数组进行排序。它基于比较操作将数组元素按特定顺序（默认是升序）排列。例如，对于一个整数数组int arr[] = {5, 3, 4, 3, 2, 5};，std::sort会将其重新排列为有序的序列，如{2, 3, 3, 4, 5, 5}。
-
然后，std::unique函数用于去除相邻的重复元素。它通过将不重复的元素移动到数组的前面部分来实现去重。在上面排序后的数组中，std::unique会将不重复的元素2, 3, 4, 5移动到数组的前面，返回一个指向去重后数组末尾的迭代器（实际上是一个指针，在数组场景下）。
-
示例代码：
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::sort(arr, arr + n);
int new_end = std::unique(arr, arr + n)-arr;
for (int i = 0; i < new_end; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
-
在这个示例中，首先计算数组的大小，然后对数组进行排序，接着使用std::unique去重，最后遍历去重后的数组部分并输出。
-
注意事项
-
std::unique只能去除相邻的重复元素，所以在使用之前通常需要先对数组进行排序。
-
它不会改变数组的大小，只是将重复的元素移到数组的末尾部分，返回的是去重后有效元素的末尾位置。
二、使用std::set容器
-
原理
-
std::set是C++ STL中的关联容器，它的特性是元素唯一。当向std::set中插入元素时，它会自动检查元素是否已经存在，如果不存在则插入，否则忽略。
-
示例代码：
#include <iostream>
#include <set>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}
-
这里首先创建一个std::set，然后遍历数组将元素插入到std::set中，最后遍历std::set输出去重后的元素。
-
注意事项
-
std::set中的元素是按照特定顺序存储的（默认是升序），如果不需要这种顺序，可以考虑使用std::unordered_set，它在插入和查找操作上可能会更高效。
-
使用std::set去重会改变元素的存储结构，并且如果需要将去重后的结果再转换回数组，需要额外的操作。
三、手动比较法（双循环法）
-
原理
-
这种方法使用两层循环。外层循环遍历数组的每个元素，内层循环用于比较当前元素与之前已经处理过的元素是否相同。如果找到相同的元素，则说明当前元素是重复的，可以跳过或者进行相应的处理。
-
示例代码：
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int new_size = 0;
for (int i = 0; i < n; i++) {
bool is_duplicate = false;
for (int j = 0; j < new_size; j++) {
if (arr[i] == arr[j]) {
is_duplicate = true;
break;
}
}
if (!is_duplicate) {
arr[new_size] = arr[i];
new_size++;
}
}
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
-
在这个示例中，new_size用于记录去重后的数组大小。外层循环每次取一个元素，内层循环检查该元素是否已经在前面出现过，如果没有则将其放入去重后的数组部分。
-
注意事项
-
这种方法的时间复杂度较高，为O(n^2)O(n2)，其中n是数组的大小。当数组规模较大时，性能可能会比较差。
-
它不需要额外的容器，但代码相对复杂一些。
四、利用std::map记录元素出现次数
-
原理
-
std::map是C++ STL中的关联容器，它以键 - 值对的形式存储数据。在这里，可以将数组元素作为键，元素出现的次数作为值。在遍历数组时，如果元素第一次出现，则将其插入std::map中，值设为1；如果元素已经存在，则将对应的值加1。最后，只遍历值为1的键，即为去重后的元素。
-
示例代码：
#include <iostream>
#include <map>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::map<int, int> m;
for (int i = 0; i < n; i++) {
if (m.find(arr[i])!= m.end()) {
m[arr[i]]++;
} else {
m[arr[i]] = 1;
}
}
for (auto it = m.begin(); it!= m.end(); it++) {
if (it->second == 1) {
std::cout << it->first << " ";
}
}
return 0;
}
-
首先创建std::map，然后遍历数组更新元素的出现次数，最后遍历std::map输出只出现一次的元素。
-
注意事项
-
这种方法使用了额外的std::map容器来存储元素的出现次数信息，会占用一定的额外空间。
-
相比于直接比较的方法，虽然时间复杂度在平均情况下可能较好，但对于一些特殊情况可能会有一定的性能开销。
五、使用std::unordered_set（哈希表去重）
-
原理
-
std::unordered_set是基于哈希表实现的关联容器。它的插入和查找操作平均时间复杂度接近常数时间O(1)O(1)。当向std::unordered_set中插入元素时，它会根据元素的哈希值快速判断元素是否已经存在，如果不存在则插入，从而实现去重。
-
示例代码：
#include <iostream>
#include <unordered_set>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::unordered_set<int> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}
-
与使用std::set类似，只是这里使用的是std::unordered_set，它在性能上可能更适合一些不需要排序且元素数量较多的情况。
-
注意事项
-
std::unordered_set的哈希函数可能会导致哈希冲突，在极端情况下可能会影响性能。不过在大多数情况下，它的性能表现较好。
-
同样，将去重后的结果转换回数组可能需要额外的操作。
六、标记法
-
原理
-
可以创建一个额外的布尔类型数组来标记已经出现过的元素。遍历原始数组时，对于每个元素，检查其在标记数组中的对应位置是否已经被标记。如果没有被标记，则说明该元素是第一次出现，将其加入去重后的结果中，并在标记数组中标记该元素；如果已经被标记，则说明是重复元素，跳过。
-
示例代码：
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
bool marked[n];
for (int i = 0; i < n; i++) {
marked[i] = false;
}
int new_size = 0;
for (int i = 0; i < n; i++) {
if (!marked[i]) {
arr[new_size] = arr[i];
new_size++;
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) {
marked[j] = true;
}
}
}
}
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
-
这里首先初始化标记数组，然后在遍历原始数组时，根据标记数组判断元素是否重复，并更新标记数组和去重后的数组。
-
注意事项
-
这种方法需要额外创建一个与原始数组大小相同的布尔类型数组来进行标记，会占用一定的额外空间。
-
它的时间复杂度取决于原始数组中重复元素的分布情况，但在最坏情况下也是O(n^2)O(n2)。
七、排序后单循环比较（优化双循环法）
-
原理
-
先对数组进行排序，这样相同的元素就会相邻。然后只需要一次循环遍历数组，比较当前元素和下一个元素是否相同。如果不同，则说明当前元素是不重复的，可以进行相应处理；如果相同，则说明是重复元素，可以跳过。
-
示例代码:
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
std::sort(arr, arr + n);
int new_size = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i]!= arr[i + 1]) {
arr[new_size] = arr[i];
new_size++;
}
}
arr[new_size] = arr[n - 1];
new_size++;
for (int i = 0; i < new_size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
-
先对数组排序，然后在循环中比较相邻元素，最后将最后一个元素处理并输出去重后的数组。
-
注意事项
-
相比于普通的双循环法，这种方法利用了排序后相同元素相邻的特性，减少了比较的次数，时间复杂度为O(nlogn + n)O(nlogn+n)，其中nlognnlogn是排序的时间复杂度，n是遍历数组的时间复杂度。
-
不过它需要先对数组进行排序，如果不需要排序后的结果，这可能会是一个额外的开销。
八、利用数组指针和动态内存分配
-
原理
-
可以创建一个动态分配内存的新数组，然后通过指针遍历原始数组。对于原始数组中的每个元素，检查它是否已经存在于新数组中。如果不存在，则将其添加到新数组中。这种方法可以避免使用一些复杂的STL容器，但需要手动管理内存。
-
示例代码:
#include <iostream>
int main() {
int arr[] = {5, 3, 4, 3, 2, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int* new_arr = new int[n];
int new_size = 0;
for (int i = 0; i < n; i++) {
bool is_duplicate = false;
for (int j = 0; j < new_size; j++) {
if (arr[i] == new_arr[j]) {
is_duplicate = true;
break;
}
}
if (!is_duplicate) {
new_arr[new_size] = arr[i];
new_size++;
}
}
for (int i = 0; i < new_size; i++) {
std::cout << new_arr[i] << " ";
}
delete[] new_arr;
return 0;
}
-
这里动态分配了一个新数组，然后通过双循环比较将不重复的元素放入新数组，最后输出并释放内存。
-
注意事项
-
这种方法需要手动管理动态分配的内存，如果忘记释放内存会导致内存泄漏。
-
双循环比较导致时间复杂度为O(n^2)O(n2)，性能在数组较大时可能较差。
九、使用std::vector和std::erase - std::remove组合（针对std::vector类型数组）
-
原理
-
在C++中，std::vector是一个动态数组容器。std::remove函数实际上并不会真正删除元素，而是将不想要的元素移到容器的末尾，并返回一个指向新的逻辑末尾的迭代器。然后std::erase函数根据这个迭代器真正地从std::vector中删除元素。
-
示例代码:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {5, 3, 4, 3, 2, 5};
v.erase(std::remove(v.begin(), v.end(), 3), v.end());
v.erase(std::remove(v.begin(), v.end(), 5), v.end());
for (auto it : v) {
std::cout << it << " ";
}
return 0;
}
-
这里先使用std::remove将指定元素（这里是3和5）移到std::vector的末尾，然后使用std::erase删除这些元素。需要注意的是，如果要去重所有元素，可能需要多次调用std::remove和std::erase或者采用更复杂的逻辑。
-
注意事项
-
这种方法主要针对std::vector类型的数组，如果是普通数组需要先转换为std::vector。
-
std::remove的使用可能会比较复杂，尤其是对于多种元素去重或者完全去重的情况。
十、自定义哈希函数去重（针对自定义类型数组）
-
原理
-
当数组中的元素是自定义类型时，可以定义一个哈希函数来计算元素的哈希值。然后可以使用类似于std::unordered_set的原理，创建一个基于自定义哈希函数的容器或者数据结构，通过比较哈希值来判断元素是否重复。
-
示例代码（假设自定义类型为MyType）:
#include <iostream>
#include <unordered_set>
struct MyType {
int a;
int b;
// 假设根据a和b计算哈希值
size_t operator()(const MyType& obj) const {
return std::hash<int>()(obj.a)^ std::hash<int>()(obj.b);
}
};
int main() {
MyType arr[] = { {1, 2}, {3, 4}, {1, 2}, {5, 6} };
int n = sizeof(arr)/sizeof(arr[0]);
std::unordered_set<MyType, MyType> s;
for (int i = 0; i < n; i++) {
s.insert(arr[i]);
}
for (auto it = s.begin(); it!= s.end(); it++) {
std::cout << "(" << it->a << ", " << it->b << ") ";
}
return 0;
}
这里定义了MyType结构体，并为其定义了一个哈希函数。然后使用std::unordered_set结合自定义哈希函数对MyType类型的数组进行去重。