寻找数组中出现次数超过一半的元素

一个数组中,有某个元素的出现次数超过数组中元素个数的一半,找出这个元素。

这题有一些较容易想到的常规做法:

  1. 先排序,中间元素即为所需元素。时间复杂度O(lonN)。
  2. 利用散列,统计每个元素出现的次数,超过一半即输出。此算法需要额外空间,约为O(n)。

不过这两种方法都未能在时间和空间上同时达到最优,在牛客网上做到这题时,评论区中有个给出了一个来源于《编程之美》中的巧妙算法,可以做到只循环一遍,且不需要额外空间。

算法基本思路是:在数组中任选两个不同元素消去,最终剩下的元素一定是出现次数超过一半的元素(在保证此元素存在的情况下)。

具体编程时,可以重头开始扫描,记录当前元素出现次数times,遇到不同的元素则times--,若times==0,换一个元素继续。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getMode(int Nums[], int n) {
int remain, times = 0;

for (int i = 0; i < n; i++) {
if (times == 0) {
remain = Nums[i];
}
if (remain == Nums[i]) {
times++;
} else {
times--;
}
}

return remain;
}

此算法需要预先保证输入元素中肯定存在解时返回结果才正确,若不确定是否有元素出现次数大于一半,需要在最后再循环检查一遍:

1
2
3
4
5
6
times = 0;
for (int i = 0; i < n; i++){
if (Nums[i] == remain)
times++;
}
return (times > n / 2 ? remain : -1);