229. 求众数 II

Difficulty
Medium
Tags
摩尔投票法
URL
https://leetcode-cn.com/problems/majority-element-ii/
Star
给定一个大小为 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)的算法解决此问题。
通过次数78,184提交次数146,063

摩尔投票

思路
首先想清楚：超过 n/3 次的元素最多有两个
其次，想清楚应该怎么初始化
题解
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        a, count_a = None, 0
        b, count_b = None, 0
        # 配对
        for n in nums[0:]:
            if n == a:
                count_a += 1
                continue
            
            if n == b:
                count_b += 1
                continue
            
            if count_a == 0:
                a = n
                count_a = 1
                continue

            if count_b == 0:
                b = n
                count_b = 1
                continue

            count_a -= 1
            count_b -= 1

        # 计数
        count_a, count_b = 0, 0
        for n in nums:
            if n == a:
                count_a += 1
            elif n == b:
                count_b += 1

        res = []
        if count_a > len(nums) // 3:
            res.append(a)
        if count_b > len(nums) // 3:
            res.append(b)
        
        return res
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。”
        x, y = None, None
        x_c, y_c = 0, 0
        for num in nums:
            # 是 x 方面军
            if (num != y) and (x_c == 0 or num == x):
                x_c += 1
                x = num
            # 是 y 方面军
            elif num == y or y_c == 0:
                y_c += 1
                y = num
            # 都不是 三者同归于尽！！
            else:
                y_c -= 1
                x_c -= 1

        # 最后判断一下幸存者是不是满足 > 3/n

        x_c, y_c = 0, 0
        for num in nums:
            if num == x:
                x_c += 1
            elif num == y:
                y_c += 1

        res = []
        if x_c > len(nums) // 3:
            res.append(x)   
        if y_c > len(nums) // 3 and x != y:
            res.append(y)  

        return res