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

思路：

  • “抵消思想”：若有一个数字出现次数超过数组长度的一半，那么将其与其他数字抵消后的结果一定大于0

1.遍历数组，记录数组可能符合的值以及次数
2.初始时假设符合要求的值为array[0]，次数为1，遍历下一个值时，若与arra[0]相同，则次数+1，否则次数-1
3.当次数减为0时，重置可能符合的值为当前位置的值，次数为1
4.最后验证遍历完数组后可能符合条件的值里记录的值，若其出现次数超过数组长度的一半，即为所求

实现：

java
  • 01
  • 02
  • 03
  • 04
  • 05
  • 06
  • 07
  • 08
  • 09
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
        if(array==null||length<=0){
            return 0;
        }
        
        int result=array[0];       //记录可能符合的数
        int time=1;
        for(int i=1;i<length;i++){
            if(time==0){              //time为0说明被抵消
                result=array[i];
                time=1;
            }else{
                if(array[i]==result){
                    time++;
                }else{
                    time--;
                }
            }
        } 
        time=0;                                //验证最后可能符合的数是否达到数组长度的一半
        for(int i=0;i<length;i++)
        {
            if(result==array[i]){
                time++;
            }
        }
        return (time > length/2) ? result : 0;
    }
}