多数元素

问题陈述

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

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

思路分析

方法一 哈希表

我们可以用一个哈希表来存储每个元素出现的次数，key为数值，value为出现次数。然后遍历HashMap寻找value大于1/2 length的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class solution{
    private Map<Integer,Integer> countNums(int[] nums){
        Map<Integer,Integer> count=new Map<Integer,Integer>();
        for(int num:nums){
            if(!count.containsKey(num)){
                count.put(num,1);
            }else{
                count.put(num,count.get(num)+1)
            }
        }
        return count;
    }
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }

}

方法二 排序

将数组进行从小到大排序，出现次数超过一半以上必定出现在中间位置。

1
2
3
4
5
6
class solution{
public int majorElement(int[] nums){
    Arrays.sort(nums);
    return nums[nums.length/2];
}
}

方法三 摩尔投票法

票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为+1 ，非众数 的票数为 -1 ，则一定有所有数字的 票数和 > 0。
票数正负抵消： 设数组 nums 中的众数为 x，数组长度为 n 。若 nums 的前 a 个数字的 票数和 =0 ，则 数组后 (n−a) 个数字的 票数和一定仍 >0，即后 (n-a)个数字的 众数仍为 x 。

算法流程:
初始化： 票数统计 votes = 0 ， 众数 x；
循环抵消： 遍历数组 nums 中的每个数字 num ；
当 票数 votes 等于 0，则假设 当前数字 num 为 众数 x ；
当 num = x 时，票数 votes 自增 1 ；否则，票数 votes 自减 1 。
返回值： 返回 众数 x 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class solution{
public int majorElement(int[] nums){
    int vote=0,x=0,count=0;
    for(num:nums){
        if(vote==0) x=num;
        vote+=num==x? 1:-1;
    }
    //验证是否为众数
    for(int num:nums){
        if(num==x) count++;
        return count>nums.length/2? x:0;
    }
  }
}