数组中出现次数超过一半的数字

来源：牛客网

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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]

对应输出应该为:

你的输出为:

因此需要加一个函数判断数组中是否存在出现次数超过一半的数字：

最终完整代码如下，数组遍历了两次，复杂度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 }