给定n个整数,其中只有一个数出现了奇数次,请找出这个数c++
时间: 2024-09-30 19:02:28 浏览: 22
在C++中,你可以使用哈希表(unordered_map)来解决这个问题,因为哈希表提供常数时间复杂度的查找操作。以下是简单的步骤:
```cpp
#include <iostream>
#include <unordered_map>
int findSingleInteger(int arr[], int n) {
std::unordered_map<int, int> countMap;
// 遍历数组,更新每个元素的计数
for (int i = 0; i < n; i++) {
countMap[arr[i]]++;
}
// 遍历map,找到唯一出现奇数次的数
for (const auto &pair : countMap) {
if (pair.second % 2 == 1) { // 如果计数值为奇数,则找到了目标
return pair.first;
}
}
// 如果没有找到这样的数,返回-1 或者抛异常(取决于需求)
return -1; // 返回默认值,表示没有找到单次出现的数
}
int main() {
int arr[] = {1, 2, 2, 3, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int result = findSingleInteger(arr, n);
std::cout << "The single integer that appears an odd number of times is: " << result << std::endl;
return 0;
}
```
在这个程序中,`findSingleInteger`函数首先创建了一个无序映射`countMap`,然后遍历数组并增加相应元素的计数。最后,它检查映射中的每个键(数字),如果计数为奇数,则返回该键。