c++中如何查找数组中的重复元素_c++数组重复元素查找方法-C++-PHP中文网

c++中如何查找数组中的重复元素_c++数组重复元素查找方法

冰火之心

发布： 2025-10-04 19:24:03

原创

669人浏览过

使用unordered_set可高效检测数组重复元素，时间复杂度O(n)，代码简洁且适用范围广。

c++中如何查找数组中的重复元素_c++数组重复元素查找方法

在C++中查找数组中的重复元素，有多种方法可以实现，根据数据规模、性能要求和是否允许修改原数组，可以选择不同的策略。以下是几种常见且实用的方法。

使用STL set或unordered_set检测重复

利用set或unordered_set的唯一性特性，遍历数组并尝试插入每个元素。如果插入失败，说明该元素已存在，即为重复元素。

特点：代码简洁，时间复杂度约为O(n)，推荐用于大多数场景。

set基于红黑树，有序，插入O(log n)
unordered_set基于哈希表，无序，平均插入O(1)

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <unordered_set>
using namespace std;
<p>void findDuplicates(int arr[], int n) {
unordered_set<int> seen;
unordered_set<int> duplicates;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < n; i++) {
    if (seen.find(arr[i]) != seen.end()) {
        duplicates.insert(arr[i]);
    } else {
        seen.insert(arr[i]);
    }
}

if (duplicates.empty()) {
    cout << "无重复元素" << endl;
} else {
    cout << "重复元素：";
    for (int val : duplicates) {
        cout << val << " ";
    }
    cout << endl;
}

登录后复制

}

排序后相邻比较

先对数组排序，然后遍历比较相邻元素。若arr[i] == arr[i+1]，则为重复。

特点：会修改原数组顺序，时间复杂度O(n log n)，空间占用小。

适用场景：不介意修改原数组，内存受限时可用。

降重鸟

要想效果好，就用降重鸟。AI改写智能降低AIGC率和重复率。

113

查看详情

#include <iostream>
#include <algorithm>
using namespace std;
<p>void findDuplicatesSorted(int arr[], int n) {
sort(arr, arr + n);
bool hasDup = false;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < n - 1; i++) {
    if (arr[i] == arr[i+1]) {
        if (i == 0 || arr[i] != arr[i-1]) { // 避免重复输出
            cout << arr[i] << " ";
            hasDup = true;
        }
    }
}
if (!hasDup) cout << "无重复";
cout << endl;

登录后复制

}

使用频次映射（map或数组计数）

统计每个元素出现次数，再输出次数大于1的元素。

适合整数数组且数值范围不大时，可用计数数组；否则用map。

#include <iostream>
#include <map>
using namespace std;
<p>void findDuplicatesMap(int arr[], int n) {
map<int, int> count;
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}</p><pre class='brush:php;toolbar:false;'>bool dup = false;
for (auto& pair : count) {
    if (pair.second > 1) {
        cout << pair.first << " ";
        dup = true;
    }
}
if (!dup) cout << "无重复";
cout << endl;

登录后复制

}

负数标记法（仅适用于正整数且值在索引范围内）

将数组本身作为哈希表使用。对于元素x，将arr[x-1]取负表示已访问。若再次访问到负值，说明重复。

限制多但空间O(1)，适合特定题目。

注意：只适用于1 ≤ arr[i] ≤ n的情况。

void findDuplicatesInPlace(int arr[], int n) {
    bool hasDup = false;
    for (int i = 0; i < n; i++) {
        int index = abs(arr[i]) - 1;
        if (arr[index] < 0) {
            cout << abs(arr[i]) << " ";
            hasDup = true;
        } else {
            arr[index] = -arr[index];
        }
    }
    if (!hasDup) cout << "无重复";
    cout << endl;
}

登录后复制

基本上就这些常用方法。选择哪种取决于具体需求：追求速度用unordered_set，节省空间考虑排序或原地标记，需要统计频次就用map。实际编码中，unordered_set方案最推荐。

以上就是c++++中如何查找数组中的重复元素_c++数组重复元素查找方法的详细内容，更多请关注php中文网其它相关文章！