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

O(n)时间复杂度
O(1)空间复杂度

• 一趟遍历，O(1)的空间消耗，意味着就地处理。
• 超过一半，意味着出现的次数多于

public class Solution {
    public int MoreThanHalfNum_Solution(int [] a) {
        int cand = a[0];
        int times = 1;
        for (int i = 1; i < a.length; i++) {
            if (times == 0) {
                cand = a[i]; // 放弃上一个候选，重新选取
                times = 1;
            } else if (a[i] == cand) {
                times++; // 候选的次数加1
            } else {
                times--; // 候选的次数消减1
            }
        }
        return cand;
    }
}