原題
給定一個(gè)整型數(shù)組般堆，找到主元素剔猿，它在數(shù)組中的出現(xiàn)次數(shù)嚴(yán)格大于數(shù)組元素個(gè)數(shù)的1/k硕糊。
給出數(shù)組[3,1,2,3,2,3,3,4,4,4]峦嗤，和 k =3蕊唐，返回 3
數(shù)組中只有唯一的主元素
解題思路
- 大體思路同Majority Element I, Majority Element II是一樣的。本題則為k-k抵消
- 維護(hù)一個(gè)hash表烁设，當(dāng)hash表中key的個(gè)數(shù)等于k的時(shí)候替梨，所有key對(duì)應(yīng)的value減一，注意如果value減一之后為零装黑，要?jiǎng)h除key
- python中dictionary相關(guān)操作
# 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
# 從新計(jì)算剩下的數(shù)字中在原數(shù)組的出現(xiàn)次數(shù)
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
