快速判断一个数组里重复值的个数
时间: 2024-01-24 11:05:35 浏览: 33
可以使用哈希表来快速判断一个数组里重复值的个数。具体步骤如下:
1. 创建一个空的哈希表,用于存储数组中的元素和它们出现的次数。
2. 遍历数组中的每一个元素,若该元素不在哈希表中,则将该元素添加到哈希表中并设置出现次数为1;若该元素已经在哈希表中,则将该元素对应的出现次数加1。
3. 遍历哈希表,统计出现次数大于1的元素的个数,即为数组中重复值的个数。
以下是使用C++语言实现的示例代码:
```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 1, 2, 4, 5, 3};
int n = sizeof(arr) / sizeof(arr[0]);
unordered_map<int, int> mp; // 哈希表
for (int i = 0; i < n; i++) {
mp[arr[i]]++; // 更新元素出现次数
}
int count = 0; // 统计重复值的个数
for (auto iter = mp.begin(); iter != mp.end(); iter++) {
if (iter->second > 1) { // 出现次数大于1
count++;
}
}
cout << "重复值的个数为:" << count << endl; // 输出结果
return 0;
}
```
输出结果为:
```
重复值的个数为:3
```
以上代码中,使用了C++11中的unordered_map来实现哈希表,并利用auto关键字遍历哈希表中的每一个元素。时间复杂度为O(n),空间复杂度为O(n)。