Majority Number III

Question

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Example Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Note There is only one majority number in the array.

Challenge O(n) time and O(k) extra space

Thoughts

依然抵消法，但是为了更快的获取，消除，增加次数，这里应该用hashtable(dictionary in python)

然后在剩下的数中找到出现次数最多的数，就是majority number(因为前提是只有一个majority number)

如果不确定，可以再loop一次找出这个数的出现次数

Solution

class Solution:
    """
    @param nums: A list of integers
    @param k: As described
    @return: The majority number
    """
    def majorityNumber(self, nums, k):
        # write your code here
        counters = {}
        for num in nums:
            if num in counters:
                counters[num] += 1
            else:
                counters[num] = 1
            if len(counters.keys()) > k:
                self.removeKey(counters)

        #recalculate remaining num occurances
        for num in counters:
            counters[num] = 0
        for num in nums:
            if num in counters:
                counters[num] += 1

        maxCounter = 0
        maxKey = 0
        for num in counters:
            if counters[num] > maxCounter:
                maxCounter = counters[num]
                maxKey = num

        return maxKey

    def removeKey(self, counters):
        l = []
        for num in counters:
            counters[num] -= 1
            if counters[num] == 0:
                l.append(num)

        for num in l:
            del counters[num]