LeetCode-229.求众数 II

LeetCode-229. 求众数 II【M】

题目描述

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

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

示例 2：

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

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示：

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

---

解题思路（摩尔投票法）

思路

  简单的思路很简单，使用哈希表存一下然后统计个数判断就行，此方法具备 $O(n)$ 的时间复杂度和 $O(n)$ 的空间复杂度。

  但是有一种更加节省空间的方法，摩尔投票法。该方法是用于寻找众数的一种简单方法，首先对最基本的情况（即从所有数字中找出出现次数大于1/2的数字）进行描述。

  简要描述摩尔投票法：该方法模拟了选举的过程，将不同的数字按他们的值分为不同的派别，每一个数字能且只能投一次票，且只能投给自己的派别支持，其余派别反对。候选数字按遍历顺序轮流更替，当当前候选人得票数为 0 的时候更换候选人。

  为了实现摩尔投票法，需要预设两个变量：c 和 s，其中 c 代表当前候选数字，s 代表该候选人的得票。遍历整个数组：

---

• 判断 s == 0 ？如果是，则更换候选数字为当前数字；否，则不操作
• 判断 c == n ？如果是，则当前候选数字票数加一；否，则减一

  遍历完成后返回当前候选数字即可。

---

证明

  考虑这种情况：对于含有 $n$ 个数字的数组求解 $c=f(n)$，前 $2k$ 个数字包含了 $k$ 个答案和 $k$ 个非答案，此时对于剩下的 $n-2k$ 个数字，$c$ 仍然是 $f(n-2k)$ 的解，如此递归，最终当 $n$ 是偶数的时候数组会剩下两个 $c$，否则将会剩下一个 $c$。

  对于上述说明，仍需要证明：如何保证一定可以向下递归，即为什么一定会出现《前 $2k$ 个数字包含了 $k$ 个答案和 $k$ 个非答案》的情况。使用反证法，若不包含这样的情况，则对于前 $2\times [\frac n 2]$ 个数字必然是非答案数字个数多于答案数字个数【若答案更多，则该情况在更前方的地方出现】。而此结果与有解相违背，故一定可以递归。

  此时的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

扩展m

  事实上，在本题中需要找到的是前 $m$ 个候选数字，即每个数字超出所有数字个数的 $[\frac n {m+1}]$，因此需要对摩尔投票法进行简单的扩展，具体来说需要维护一个长度为 $m$ 的字典，并遍历每个数字：

• 判断 $m$ 个候选数字是否有空席 以及 $m$ 个候选数字是否有的得票数为零
  • 如果有，则将要被替换的候选数字席位置空，并将当前数字加入候选数字
  • 否则，不操作
• 判断当前 $m$ 个候选数字的派别，投出赞同票或反对票
• 统计当前 $m$ 个候选数字的个数，返回符合题意的数字列表

代码

class Solution:
    def majorityElement(self, nums: List[int], m: int) -> List[int]:
        m -= 1
        re = []
        dic = {}
        for n in nums:
            for k in list(dic):
                if dic[k] == 0:
                    del dic[k]
            if len(dic) < m and n not in dic:
                dic[n] = 0
            devote = 0 if n in dic else 1
            for k in dic:
                if k == n:
                    dic[k] += 1
                else:
                    dic[k] -= devote

        for k in dic:
            if sum([1 if i==k else 0 for i in nums]) > len(nums)//m:
                re.append(k)
        return re