数组中有一个数字出现的次数超过数组长度的一半,请找出这个数 字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在 数组中出现了 5 次,超过数组长度的一半,因此输出 2。如果不存在 则输出 0。 要求:时间复杂度不能超过 O(n)。
时间: 2024-03-06 13:50:53 浏览: 25
这道题可以使用摩尔投票法(Moore Voting)来解决,时间复杂度为 O(n)。
算法流程如下:
1. 假设数组中的第一个数是众数,设置计数器 count = 1。
2. 从数组的第二个数开始遍历,如果当前的数与假设的众数相同,计数器加一,否则计数器减一。
3. 如果计数器 count 的值为零,将当前数设为假设的众数,并将计数器 count 设为 1。
4. 遍历完整个数组之后,假设的众数就是出现次数超过一半的数字,但需要再次遍历数组来确定它是否真的是众数。
代码实现如下:
```
int findMajority(vector<int>& nums) {
int n = nums.size();
int count = 1, majority = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] == majority) {
count++;
} else {
count--;
}
if (count == 0) {
majority = nums[i];
count = 1;
}
}
count = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == majority) {
count++;
}
}
return count > n / 2 ? majority : 0;
}
```
其中,第一次遍历数组找出假设的众数,第二次遍历数组验证这个众数是否是真正的众数,如果是,返回该众数,否则返回 0。
时间复杂度为 O(n),空间复杂度为 O(1)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)