原题
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。
给出数组[3,1,2,3,2,3,3,4,4,4]，和 k =3，返回 3
数组中只有唯一的主元素
解题思路
- 大体思路同Majority Element I, Majority Element II是一样的。本题则为k-k抵消
- 维护一个hash表，当hash表中key的个数等于k的时候，所有key对应的value减一，注意如果value减一之后为零，要删除key
- python中dictionary相关操作
# get all the keys of a dictionary
dict.keys()
# delete a key in dictionary
dict.pop(key, None) # or dict.pop(key)
完整代码
class Solution:
"""
@param nums: A list of integers
@param k: As described
@return: The majority number
"""
def removeKey(self, counters):
keySet = counters.keys()
removeList = []
for key in keySet:
counters[key] -= 1
if counters[key] == 0:
removeList.append(key)
for key in removeList:
counters.pop(key, None)
def majorityNumber(self, nums, k):
counters = {}
for num in nums:
if num not in counters:
counters[num] = 1
else:
counters[num] += 1
if len(counters) >= k:
self.removeKey(counters)
if len(counters) == 0:
return -1
# 从新计算剩下的数字中在原数组的出现次数
for key in counters.keys():
counters[key] = 0
for num in nums:
if num in counters:
counters[num] += 1
# find the max key
maxCounter, maxKey = 0, 0
for key, value in counters.iteritems():
if value > maxCounter:
maxCounter = value
maxKey = key
return maxKey
