给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

把狂野般的思绪收一收，咱们来看看最优解。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;//当前答案出现的次数
        Integer candidate = null;//答案
 
        for (int num : nums) {
            if (count == 0) candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
 
        return candidate;
    }
}

我来解释一下策略：记录当前的答案candidate ，记录count。这时，我们遍历了一个新的数字，如果和candidate 一样，我们就让count+1，否则让count-1.如果count变成了0，那candidate 就下擂台，换新的擂主（数字）上，也就是说把candidate 更新成新的数字，count也更新成1.

最后在擂台上的一定是答案。

肯定有人怀疑这个做法的正确性吧？我就来说一下它为啥对？

首先，我们想像一下对最终隐藏答案ans最不利的情况：每个其他数字全部都打擂这个答案ans，那ans的count最后也会剩1，不会被打下来。

正常情况呢？其他数字还会互相打擂，这些数字如此“内耗”，又怎么能斗得过最终答案ans呢？对不对？