LeetCode 169. Majority Element [Easy]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：https://leetcode.com/problems/majority-element

题目难度：Easy

解答1[Java]（Boyer-Moore Voting Algorithm）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

分析

这个算法叫做摩尔投票法（Boyer-Moore Voting Algorithm）。

选定一个数，遇到相同的就加1，不同就减1，count 变成 0 就换下一个数，因为众数占总体的一半以上，所以众数总能脱颖而出。

时空复杂度

时间复杂度：$O(n)$

空间复杂度：$O(1)$

解答2[Java]

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

分析

因为众数的数量大于 $\lfloor n/2 \rfloor$，则众数的数量最小为 $\lfloor n/2 \rfloor + 1$。

如果我们对数组进行排序，有三种情况：

① 假设众数比所有数都小，则众数将占据排序后数组的左半部分。

② 如果众数比所有数都大，则众数将占据排序后数组的右半部分。

③ 如果数组不是最大的也不是最小的，众数将占据排序后数组的中间部分。

不管哪一种情况，排序后的数组中的第 $\lfloor n/2 \rfloor + 1$ 个位置上的数一定是众数。

时空复杂度

时间复杂度：$O(nlogn)$，本算法的主要开销在排序上，因此时间复杂度就是快速排序的时间复杂度。

空间复杂度：$O(1)$

参考资料

  1. Majority Element - LeetCode Articles
  2. MisterBooo/LeetCodeAnimation 169. Majority Element