LeetCode97 - 多数元素 | 很多时候不懂事

📝 题目描述

题目链接：多数元素

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

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

示例：

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
输入保证数组中一定有一个多数元素。

💡 解题思路

方法一：哈希表

最容易想到的方法，我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值大于⌊ n/2 ⌋。

也可以在遍历数组 nums 时候，“++”完立刻比较并维护最大的值，这样省去了最后对哈希映射的遍历。

方法二：排序

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 $\lfloor \frac{n}{2} \rfloor$ 的元素（下标从 0 开始）一定是众数。

对于这种算法，我们先将 nums 数组排序，然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是 n 为奇数的情况，第二个例子是 n 为偶数的情况。

对于每种情况，数组上面的线表示如果众数是数组中的最小值时覆盖的下标，数组下面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况，这条线会在这两种极端情况的中间。对于这两种极端情况，它们会在下标为 $\lfloor \frac{n}{2} \rfloor$ 的地方有重叠。因此，无论众数是多少，返回 $\lfloor \frac{n}{2} \rfloor$ 下标对应的值都是正确的。

方法三：摩尔投票算法

如果我们把众数记为 $+1$ ，把其他数记为 $−1$ ，将它们全部加起来，显然和大于 $0$ ，从结果本身我们可以看出众数比其他数多。核心思想是：

每次消去两个不同的元素。如果某个元素的数量超过总数的一半，那么它一定不会被全部消掉。

假设多数元素是 A。题目保证：

$A 的数量 > 其他所有元素的数量之和$

注意是比其他元素加起来还多，而不只是比其中任何一种多。现在，每次从数组中删除两个值不同的元素，只可能有两种情况：

删除一个 $A$ 和一个其他元素：双方数量都减一， $A$ 仍然比其他元素的总数多。
删除两个其他元素： $A$ 的数量不变，其他元素减少， $A$ 的优势更大。

因此，删除两个不同的元素，不会改变谁是多数元素。不断抵消，直到剩下的元素都相同，剩下的就一定是 $A$ 。

具体到实现上，我们使用变量 candidate 表示当前候选人，也就是目前未被抵消的元素的值；使用变量 count 表示目前有多少个这样的元素尚未被抵消。

遍历数组，对于当前元素 x，执行以下规则：

如果 count == 0：说明之前积累的元素已经全部抵消。让 x 成为新候选人，并设置 count = 1。
如果 x == candidate：同类元素无法互相抵消，把它留下，count += 1。
如果 x != candidate：让 x 与一个候选人元素抵消，count -= 1。

在遍历过程中，candidate 会变换，但最后留下的一定是多数元素。

🔧 代码实现

1、哈希表

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> mp;
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            mp[nums[i]]++;
        }
        for (pair<const int, int>& k : mp){
            if (k.second > (nums.size()/2)) {
                res = k.first;
                break;
            }
        }
        return res;
    }
};

2、排序

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

3、摩尔投票算法

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0, count = 0;
        for (auto& num : nums) {
            // 与候选人相同，数量++
            if (candidate == num) {
                count++;
            } else {
                // 不相同则先判断数量
                if (count) {
                    // 不为零则减少
                    count--;
                } else {
                    // 为零则替换候选人
                    candidate = num;
                    count++;
                }
            }
        }
        return candidate;
    }
};

📊 复杂度分析

1、哈希表

时间复杂度： $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度，遍历数组 $nums$ 一次，对于 $nums$ 中的每一个元素，将其插入哈希表都只需要常数时间。
空间复杂度： $O(n)$ ，哈希表最多包含 $n - \lfloor \frac{n}{2} \rfloor$ 个键值对，所以占用的空间随着输入的规模增大。

2、排序

时间复杂度： $O(nlogn)$ ，这是将数组排序的时间复杂度。
空间复杂度： $O(logn)$ ，如果使用语言自带的排序算法，需要使用这些栈空间。

3、摩尔投票算法

时间复杂度： $O(n)$ ，只对数组进行了一次遍历。
空间复杂度： $O(1)$ ，算法只需要常数级别的额外空间。

🎯 总结

核心思想：技巧性题目，本身不难，只不过引出了特别的算法。