動機

太偏門了吧

Problem

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

 

Example 1:

Input: nums = [3,2,3]Output: [3]

Example 2:

Input: nums = [1]Output: [1]

Example 3:

Input: nums = [1,2]Output: [1,2]

 

Constraints:

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

Sol

看看資料規模，先暴力

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        return [k for (k,v) in filter(lambda kv: kv[1] > len(nums)//3, Counter(nums).items())]

題目有一個條件，數字個數大於n/3個

那這個數字最多幾種?

n/3 <= x
n <= 3x # 如果有三個這種數字，就會超過n

所以最多兩個，之後要在O(n)中常數記憶體找最多數就是Moore vote

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        rets = [0]*2
        cnts = [0]*2
        for n in nums:
            if rets[0] == n:
                cnts[0] += 1
            elif rets[1] == n:
                cnts[1] += 1
            elif cnts[0] == 0:
                rets[0] = n
                cnts[0] = 1
            elif cnts[1] == 0:
                rets[1] = n
                cnts[1] = 1
            else:
                cnts[0] -= 1
                cnts[1] -= 1
        
        cnts = [0]*2
        for n in nums:
            if rets[0] == n:
                cnts[0] += 1
            elif rets[1] == n:
                cnts[1] += 1
        
        ret = []
        [ret.append(rets[i]) for i in range(2) if cnts[i] > len(nums)//3]
        return ret