题解 | #数组中出现次数超过一半的数字#

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int max = -1;
        int count = 0;
        for(int i = 0; i < array.length; i++){
            if(max != array[i]){
                if(count == 0){
                    max = array[i];
                    count = 1;
                }else{
                    count--;
                }
            }else{
                count++;
            }
        }
        return max;
    }
}

[1,2,3,2,2,2,5,4,2]

一开始假设超过一般的值就是1，然后遍历，

i = 0，max = 1，count = 1

i = 1，（arr[i] = 2） != max，这时候count != 0, count--

i = 2, （arr[i] = 3） != max, 这时候count = 0，max= arr[i] = 3, count = 1

i = 3, （arr[i] = 2） != max, 这时候count != 0, count--，count = 0

i = 4，（arr[i] = 2） = max，这时候count = 0，max = arr[i] = 2，count = 1

i = 5，（arr[i] = 2）= max， 这时候count++，count = 2

i = 6，（arr[i] = 5）!= max, 这时候count != 0, count--，count = 1

i = 7，（arr[i] = 4）!= max, 这时候count != 0, count--，count = 0

i = 7，（arr[i] = 2）== max, 这时候count != 0, count++，count = 1

最终结果：max = 2，在这个过程中，假设当前数是最多的数，遍历，遇到不同的数，票数 - 1，如果票数 = 0，证明了当前的数不是最多的数，因为最多的数超过了数组长度一半，所以这个数的票数肯定能抵消其他的。