169. 求众数(easy)

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 $⌊ n/2 ⌋$ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 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

上面列出了三种求众数的方法，其中代码一是比较通用的方法—摩尔投票法，此题中众数定义为出现次数大于 $n/2$ 的数，所以我们可以进行计数，后面的数相同则加一，不同就减一，如果到了0则换下一个数，最后出现次数最多的数一定会留下来，只需要遍历一次数组，而且其计数肯定大于0，最后返回现有保存的数即是我们要求的众数。
代码二则时间复杂度较高，但是比较容易想到，直接排序取中间的数即可。
代码三则时间复杂度较优，利用set减少遍历次数，然后直接利用python内置函数count进行计数，简单粗暴。

169. 求众数(easy)

推荐阅读更多精彩内容