给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于
的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
- show the code:
### code1:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cur,count = nums[0],1
for i in range(1,len(nums)):
if count == 0:
cur = nums[i]
if cur == nums[i]:
count += 1
else:
count -= 1
return cur
### code2
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sorted(nums)[len(nums)//2]
### code3:
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for num in set(nums):
if nums.count(num) > len(nums)/2:
return num
- 上面列出了三种求众数的方法，其中代码一是比较通用的方法—摩尔投票法，此题中众数定义为出现次数大于
的数，所以我们可以进行计数，后面的数相同则加一，不同就减一，如果到了0则换下一个数，最后出现次数最多的数一定会留下来，只需要遍历一次数组，而且其计数肯定大于0，最后返回现有保存的数即是我们要求的众数。
- 代码二则时间复杂度较高，但是比较容易想到，直接排序取中间的数即可。
- 代码三则时间复杂度较优，利用
set减少遍历次数，然后直接利用python内置函数count进行计数，简单粗暴。
