C++实现:已知在一个int数组中,有一个数字出现超出了一半,找出该数字.补充find函数,传入参数为数组首地址和数组长度,返回该数字.
时间: 2024-09-29 07:05:00 浏览: 51
基于C++编写一个函数求一个4*4二维数组所有周边元素的和
在C++中,你可以使用哈希表(unordered_map)或双指针法(一种空间复杂度为O(1)的算法)来解决这个问题。这里我们提供一个使用双指针法的简单示例:
```cpp
#include <unordered_map>
#include <vector>
int findDuplicate(int* nums, int length) {
if (length <= 1) return -1; // 如果数组为空或只有一个元素,不存在超一半的数
std::unordered_map<int, int> countMap;
for (int i = 0; i < length; ++i) {
if (countMap.find(nums[i]) != countMap.end()) { // 如果当前元素已经存在,说明找到了超一半的数
return nums[i];
}
countMap[nums[i]]++; // 更新计数
}
// 如果遍历完整个数组都没有找到超一半的数,返回-1
return -1;
}
```
在这个函数中,`findDuplicate`接收一个整型数组的指针和它的长度。通过遍历数组,我们检查每个元素出现的次数,并将其存储在`countMap`中。如果某个元素的计数值大于它在数组中的位置减一(因为不可能超过一半),那么这个元素就是我们要找的答案。
阅读全文