Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路：
- 继续使用collections的Counter方法。
- 对list排序，数组长度的一半的地方就是最多元素。
- Boyer-Moore算法，高人的算法果然很厉害，我看了好几遍才明白。设置两个变量majority和count，都设为0.依次遍历list。如果count为0，则重选majority；如果当前数字和majority相等，count加一，否则减一。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
import collections
if not nums:
return 0
if len(nums) == 1:
return nums[0]
return [n for n, count in collections.Counter(s).items() if count > len(nums)//2][0]
def majorityElement2(self, nums):
if not nums:
return 0
nums.sort()
return nums[len(nums)/2]
def majorityElement3(self, nums):
if not nums:
return 0
dic = {}
for num in nums:
dic[num] = dic.get(num, 0) + 1
for num in nums:
if dic[num] > len(nums)//2:
return num
def majorityElement4(self, nums):
if not nums:
return 0
majority = 0
count = 0
for num in nums:
if count == 0:
majority = num
if num==majority:
count += 1
else:
count -= 1
return majority
if __name__ == '__main__':
sol = Solution()
s = [1, 1, 2, 1, 2, 2, 1, 2, 2]
print sol.majorityElement(s)
print sol.majorityElement2(s)
print sol.majorityElement3(s)
print sol.majorityElement4(s)
