LintCode Q47 Majority Number II in Python

  • Jinhai ZHOU
  • 6 Minutes
  • 2016年11月24日
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
43
44
45
46
47
48
49
50
class Solution:
"""
@param nums: A list of integers
@return: The majority number occurs more than 1/3
"""
def majorityNumber(self, nums):
# write your code here
# time O(n)
# space O(1)
if len(nums) == 0:
return
candidate1, count1 = None, 0
candidate2, count2 = None, 0
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
elif count1 == 0:
candidate1 = num
count1 += 1
elif count2 == 0:
candidate2 = num
count2 += 1
else:
count1 -= 1
count2 -= 1
res = self.validate(nums, candidate1, candidate2)
if res is None:
return nums[0]
else:
return res
def validate(self, nums, candidate1, candidate2):
if candidate1 is None:
return candidate2
if candidate2 is None:
return candidate1
count1, count2 = 0, 0
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
if count1 >= count2 and count1 > len(nums)/3:
return candidate1
elif count2 >= count1 and count2 > len(nums)/3:
return candidate2
else:
return None
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。