目录

0229:多数元素 II(★)

力扣第 229 题

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

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

相似问题:

分析

0169 升级版,可以直接计数,也可以考虑摩尔投票法。

  • 在 nums 中任意消除三个不同的数直到剩下两种数或一种数
  • 假如 nums 中存在超过 ⌊ n/3 ⌋ 次的元素,那么该元素必然会留下来
  • 因此检查最终留下来的数是否符合即可

这可以推广到求超过 ⌊ n/k ⌋ 次的元素。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        ct = defaultdict(int)
        for x in nums:
            ct[x] += 1
            if len(ct)==3:
                for x in list(ct):
                    ct[x] -= 1
                    if not ct[x]:
                        del ct[x]
        return [x for x in ct if nums.count(x)>len(nums)//3]

38 ms