LintCode Q46 Majority Number with validation in Python

  • Jinhai ZHOU
  • 4 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
class Solution:
"""
@param nums: A list of integers
@return: The majority number
"""
def majorityNumber(self, nums):
# write your code here
# time O(n)
# space O(1)
if len(nums) == 0:
return
candidate = None
count = 0
for num in nums:
if candidate is None:
candidate = num
count += 1
elif candidate != num:
count -= 1
if count == 0:
candidate = None
else:
count += 1
if candidate is not None and self.validate(nums, candidate):
return candidate
else:
return nums[0]
def validate(self, nums, candidate):
count = 0
for num in nums:
if num == candidate:
count += 1
return count > len(nums)/2
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。