题目描述

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

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

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2

https://leetcode-cn.com/problems/majority-element/

解法1

使用Map统计每个数出现的频率，当发现元素e出现的频率超过⌊ n/2 ⌋时，返回元素e。时间复杂度与空间复杂度均为O(n)

解法2

对数组排序，然后返回中间元素。因为元素e超过了⌊ n/2 ⌋，那么排序后数组的中间位置已定是元素e。时间复杂度O(nlogn)，空间复杂度O(1)

解法3

该方法被称为Boyer-Moore majority vote algorithm。设置变量majority与counter。依次遍历每个元素e，当计数器counter为0时，将e赋给majority，设置counter为1；此后的循环，当发现e==majority时，counter自增1；当发现e!=majority时，counter自减1。

该算法执行完毕时，若存在频率高于⌊ n/2 ⌋的元素，则majority存放的就是答案。如果不存在频率高于⌊ n/2 ⌋的元素，则该算法并不能识别出这种情况。需要再次扫描统计majority出现的频率。

但是本题给定了说明一定存在众数，我们就只需要扫描一次然后返回majority变量即可。全部代码如下。

class Solution {
    public int majorityElement(int[] nums) {
        int majority = 0;
        int counter = 0;

        // https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
        
        for (int num : nums) {
            if (num == majority)
                counter++;
            else if (counter == 0) {
                majority = num;
                counter = 1;
            } else
                counter--;
        }

        return majority;
    }
}