Leetcode-229题:Majority Element2

题目：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.

思路：现在要求找出出现次数大于n/3的数字，那么这个数字可能不存在，可能有1个，也可能有2个。如果不要求空间复杂度是O(1)的话，只要扫描一遍数组统计各个数字出现的次数即可。但要求O(1)空间复杂度就只能通过维护几个计数器来完成任务，那么就应该通过一种方法来缩小候选的数字集合，缩小到常数个。所采用的方法与169题相似，每次删除三个不同的数字，直到不存在三个不同的数字。这时要注意的是，满足要求的数字一定出现在剩余数字中，但是剩余数字不一定都满足要求，可通过再一次扫描数组，统计出剩余的数字出现的次数，判断是否满足要求即可。

代码：

def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    if nums == None:
        return None
    result = []
    num_counter = {}
    for n in nums:
        if n in num_counter:
            num_counter[n] += 1
        elif len(num_counter) < 2:
            num_counter[n] = 1
        else:
            for k,v in num_counter.items():
                if v == 1:
                    num_counter.pop(k)
                else:
                    num_counter[k] -= 1
    for k in num_counter.keys():
        num_counter[k] = 0
    for n in nums:
        if n in num_counter:
            num_counter[n] += 1
    for k,v in num_counter.items():
        if v > len(nums)/3:
            result.append(k)
    return result