【leetcode常见面试题】169. 多数元素

【主要考察点】：哈希表、排序

解题方法

1. 哈希表

直接利用哈希表记录每个元素出现的次数，一旦发现某个元素出现的次数超过数组长度的一半，则表示找到目标值。

时间复杂度O(n)
空间复杂度O(n)

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = nums.length / 2 + 1;
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) == cnt){
                return num;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 排序

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length / 2 + 1;
        int cnt = 1;

        if(len == 1){
            return nums[0];
        }

        for(int i = 1; i<nums.length; i++){
            if(nums[i] == nums[i - 1]){
                cnt += 1;
            }else{
                cnt = 1;
            }
            if(cnt == len){
                return nums[i];
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

排序的方式还可以直接得到结果

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

3. 摩尔投票法

因为题干中已经说明：多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素，也就是求解的众数比其他所有数加起来都要多，那么就可以通过抵消的方式来完成本题。

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int result = nums[0];
        for (int num : nums) {
            if (cnt == 0) {
                result = num;
            }
            if (num == result) {
                cnt += 1;
            } else {
                cnt -= 1;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17