LintCode Q48 Majority Number III in Python

  • Jinhai ZHOU
  • 5 Minutes
  • 2016年11月25日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys
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
candidates = {}
for num in nums:
if num in candidates:
candidates[num] += 1
elif len(candidates) < k- 1:
candidates[num] = 1
else:
for key in candidates.keys():
candidates[key] -= 1
if candidates[key] == 0:
del candidates[key]
res = self.validate(nums, k, candidates)
if res is not None:
return res
else:
return
def validate(self, nums, k, candidates):
max_key, max_count = -sys.maxint - 1, -sys.maxint - 1
for key in candidates:
candidates[key] = 0
for num in nums:
if num in candidates:
candidates[num] += 1
for key, count in candidates.iteritems():
if count > max_count:
max_count = count
max_key = key
if max_count > len(nums)/k:
return max_key
else:
return None
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。