题目描述

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

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

样例

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

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

算法1

• 用哈希表记录每个元素出现多少次，最后枚举整个哈希表，找到出现次数最多的元素

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = nums.length;
        for(int i = 0;i < n;i ++) 
        {
            int x = nums[i];
            map.put(x, map.getOrDefault(x, 0) + 1);
        }


        int res = 0;
        int count = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            if(entry.getValue() > count)
            {
                count = entry.getValue();
                res = entry.getKey();
            }
        }

        return res;
    }
}

算法2

投票法

维护两个变量：候选人和他的票数

• 1、候选人初始化为r = 0，票数c初始化为0
• 2、当票数为0时，更换候选人，将票数重置为1
• 3、向后遍历数组，遇到相同元素票数加1，否则减1
• 4、遍历完数组，当前候选人即为数组中出现的多数元素

上面操作方法一定是正确的，假设当前x的次数出现最多，假设x不是返回的答案，又因为x需要通过与 x不同的数 才会进行消耗，可是与x不同的数的个数 一定 比 x 少，因此x一定不会被完全消耗掉，因此假设矛盾

时间复杂度 $O(n)$

Java 代码

class Solution {
    public int majorityElement(int[] nums) {
        int r = 0,c = 0;
        for(int i = 0;i < nums.length;i ++)
        {
            int x = nums[i];
            if(c == 0) {r = x; c = 1;}
            else if(r == x) c ++;
            else c --; 
        }

        return r;
    }
}