Majority Number II

题目描述

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

解题方法

注意这里要的是所有的结果，而不是某一个数

brute force

hashmap, count

消去法

N/3, 最多有两个结果。

• 模仿moore's voting algorithm,用两个变量和counter记录
• 如果当前值等于其中某一个，就将对应的counter + 1
• 如果某一个counter为0了，就将对应的变量设为当前值，counter设为1
• 如果当前num都不等于就两个counter都减去1
• 当任一一个counter为0时就将变量设为当前的num
• 最后剩下的两个value还要再loop一遍得到次数来验证是否是majority number
  • 不要忘了验证
  • 不要忘了验证
  • 不要忘了验证（重要的事情说三遍）

注意点

• 先判断等于，再判断counter，这样可以避免两个变量变成相同的数

Solution

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        if length == 0:
            return []
        if length == 1:
            return nums
        if length == 2:
            if nums[0] == nums[1]:
                return [nums[0]]
            else:
                return nums

        a, b = None, None
        countA, countB = 0, 0
        for num in nums:
            if num == a:
                countA += 1
            elif num == b:
                countB += 1
            elif countA == 0:
                a = num
                countA = 1
            elif countB == 0:
                b = num
                countB = 1
            else:
                countA -= 1
                countB -= 1

        countA = 0
        countB = 0
        for num in nums:
            if num == a:
                countA += 1
            elif num == b:
                countB += 1
        if countA > length / 3.0 and countB > length / 3.0:
            return [a, b]
        elif countA > length / 3.0:
            return [a]
        elif countB > length / 3.0:
            return [b]
        else:
            return []

Reference