LintCode Q46 Majority Number in Python

  • Jinhai ZHOU
  • 3 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
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)
stack = []
count = 0
for num in nums:
if len(stack) == 0:
count = 1
stack.append(num)
elif stack[-1] != num:
count -= 1
if count == 0:
stack.pop()
else:
count += 1
if len(stack) == 0:
return nums[0]
else:
return stack[-1]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。