给出n个整数,n为奇数。其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。 请找出出现了奇数次的那个整数。给出代码
时间: 2024-09-16 22:04:02 浏览: 7
这个问题可以通过哈希表(unordered_map)来解决。遍历数组,对于每个元素,检查其出现次数。如果当前元素已经在哈希表中,则减少它的计数;否则增加计数。因为只有一个是奇数次出现,所以当遇到第一个计数为奇数的元素时,就是我们要找的答案。
以下是C++代码实现:
```cpp
#include <unordered_map>
int findSingle(int arr[], int n) {
std::unordered_map<int, int> countMap;
// 遍历数组,更新元素的出现次数
for (int i = 0; i < n; i++) {
countMap[arr[i]]++;
}
// 再次遍历数组,查找出现次数为奇数的元素
for (int i = 0; i < n; i++) {
if (countMap[arr[i]] % 2 == 1) {
return arr[i];
}
}
// 如果没有找到,返回-1 或者抛异常,这里假设找不到则返回-1
return -1;
}
// 示例用法
int main() {
int arr[] = {1, 2, 3, 4, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int result = findSingle(arr, n);
std::cout << "The number that appears odd times is: " << result << std::endl;
return 0;
}
```
在这个代码中,`findSingle` 函数接受一个整数数组 `arr` 和长度 `n`,然后使用哈希表 `countMap` 存储每个元素及其出现次数。第一次遍历结束后,哈希表中的键值对表示了所有元素的出现次数。第二次遍历时,只要发现某个元素的计数是奇数,就立即返回这个元素。如果没有找到这样的元素,函数返回 -1(实际应用中可以根据需求修改返回值或处理方式)。