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

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

解题思路

Boyer-Moore 投票算法

把多数元素看作是“英雄”，其他元素看作是“平民”。

• 遍历数组，选取第一个元素作为英雄
• 如果两个英雄相遇，他们继续在一起（count++）
• 如果一个英雄遇到一个平民，他们同归于尽（count--）
• 如果两个平民遇到，也同归于尽（count--）
• 如果英雄被抵消了（count为0），就选取下一个元素作为英雄

因为英雄的人数超过了总人数的一半，即使所有平民都联合起来对抗英雄，最后剩下的也一定是英雄。

Java实现

    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;
        for (int num : nums){
            if (count == 0){
                candidate = num;
            }
            
            if (num == candidate){
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }