M-NR 229. Majority Element II

M

Loading...LeetCode

能看懂, 但是还不是太理解为啥能work.

https://leetcode.com/problems/majority-element-ii/discuss/63520/Boyer-Moore-Majority-Vote-algorithm-and-my-elaboration

题目要求O(n), O(1),自然不能用169的第一个做法了.

class Solution:
    def majorityElement(self, nums):
        if not nums:
            return []
        count1, count2, candidate1, candidate2 = 0, 0, 0, 1
        for n in nums:
            if n == candidate1:
                count1 += 1
            elif n == candidate2:
                count2 += 1
            elif count1 == 0: # count==0的时候, 此时candidate的值并不重要, 因为其freq已经下降到0
                candidate1, count1 = n, 1 #  所以我们为其赋上新值n和新freq -> 1.
            elif count2 == 0:
                candidate2, count2 = n, 1
            else:
                count1, count2 = count1 - 1, count2 - 1
        return [n for n in (candidate1, candidate2)
                        if nums.count(n) > len(nums) // 3]