Majority Number III

题目描述

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.

解题方法

brute force

hashmap记录次数

消去法

思路是类似的，但是这里可以不要用k-1个变量和counter，可以用一个hashtable 来记录变量和counter。

for num in nums:
    if num in counters:
        counters[num] += 1
    else:
        counters[num] = 1
    if len(counters.keys()) > :
        self.removeKey(counters)

这里ermoveKey()是将counters里所有的number都减去1，然后将number为0的value删掉

最后再验证一下

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]

Reference