剑指Offer-数组中出现次数超过一半的数字

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

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的
数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出
2。如果不存在则输出0。

思路

count计数器，一样的+1，不一样的-1，当减到0的时候，以下一个数字为基准，再计数。
需要最终有个判断，一次遍历。

代码

public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            if(array==null){
                return 0;
            }
            int count=0;
            int mainNum=0;

            for(int i=0;i<array.length;i++){
                 if(count==0){
                    mainNum=array[i];
                     count=1;
                }else if(mainNum==array[i]){
                    count++;
                }else{
                    count--;
                }          
            }
            int sum=0;
            for(int i=0;i<array.length;i++){//判断结果是否正确
                if(array[i]==mainNum){
                    sum++;
                }
            }

            if(sum>array.length/2){
                return mainNum;
            }

            return 0;

        }
}