来源：牛客网
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 思路：一个数字出现次数超过了一半，可以证明，若每次从数组中取出两个不同的数，剩下的数组中，该数字依旧超过了一半。 因此设计如下算法： 定义一个栈，遍历数组a[] 若栈空，将a[i]入栈； 若不空，比较top元素与a[i]， 若相等，a[i]入栈，i++； 若不等，top元素出栈，i++； 最后栈里剩下都是同一个元素，且是超过一半的数字。 其实不用栈可以，代码如下：1 public static int MoreThanHalfNum_Solution(int [] array) {
2 int candidate=0, times=0;
3 for(int i=0; i<array.length; ++i){
4 if(0==times) {
5 candidate=array[i];
6 times++;
7 } else{
8 if(candidate==array[i]) times++;
9 else times--;
10 }
11 }
12
13 return candidate;
14 }
然而提交的时候却并没有AC，原因是漏了一个条件：若不存在则返回0。
测试用例:
[1,2,3,2,4,2,5,2,3]
对应输出应该为:
0
你的输出为:
3
因此需要加一个函数判断数组中是否存在出现次数超过一半的数字： 最终完整代码如下，数组遍历了两次，复杂度O(2n). 加了一行检测输入数组是否空。1 public class Solution {
2 public int MoreThanHalfNum_Solution(int [] array) {
3 if(array==null) return 0;
4 int candidate=0, times=0;
5 for(int i=0; i<array.length; ++i){
6 if(0==times) {
7 candidate=array[i];
8 times++;
9 } else{
10 if(candidate==array[i]) times++;
11 else times--;
12 }
13 }
14 if(checkIfExits(array, candidate)) return candidate;
15 else return 0;
16 }
17
18 public boolean checkIfExits(int[] a, int c){
19 int times=0;
20 for(int i=0; i<a.length; ++i){
21 if(c==a[i]) times++;
22 }
23 if(times>a.length/2) return true;
24 else return false;
25 }
26 }