[NC]73. 数组中出现次数超过一半的数字

🚩传送门：牛客题目

其他解法：Ar 169. 多数元素

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：Boyer-Moore 投票算法

对于投票算法，最多一个 和 一个 杂数 相互抵消掉，如果 杂数 和 杂数 相互抵消 ，那么统计的值更大更有利 。

复杂度分析

时间复杂度：。 算法只对数组进行了一次遍历。

空间复杂度：。算法只需要常数级别的额外空间。

官方代码

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int sum=0;
        int res=0;
        for(int i=0;i<array.length;++i){
            if(sum==0) res=array[i];
            sum+=(array[i]==res)?1:-1;
        }
        return res;
    }
}