leetcode [229] 求众数 II

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

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

示例 2:

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

思路来自题解：

维护两个数，并记录他们出现的次数。遇到新的数，如果在已知数中，加计数，如果不在，从次数最少的开始减1，如果出现-1，更新为当前值，次数置为1，处理新的数。从次数最少的开始减的原因是，每次只能让一个数更新，否则会导致两个数都减为0，无法处理[1,2,3,4,5]这样的情况。

from collections import defaultdict
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1: return nums

        candd = defaultdict(int)
        for n in nums:
            if len(candd) < 2 or n in candd:
                candd[n] += 1
                continue
            for k in sorted(candd.keys(), key=lambda x: candd[x]):
                candd[k] -= 1
                if candd[k] == -1:
                    del candd[k]
                    candd[n] = 1
                    break
        
        res = []
        for k in candd.keys():
            if sum(1 for n in nums if n == k) > len(nums) // 3:
                res.append(k)

        return res