「求众数」| leetcode 刷题010

题目

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]

输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]

输出: 2

解答

乍一看，这道题思路清晰，而且题目还给出提示，照理来说，应该这样写:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in nums:
            if nums.count(i) > len(nums)/2:
                return i
           

这样一写必然出错，为啥，太耗时间，计算的次数太多不行的。

那怎么写呢

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num = {}
        for i in nums:
            if i in num:
                num[i] += 1

            else:
                num[i] = 1
        return max(num.items(),key = lambda x:x[1])[0]
           

可以这样写，构造一个字典，求出字典中 key 的最大值。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        for num in nums:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        for k, v in d.items():
            if v > len(nums) // 2:
                return k
           

这样也可以。

看一下大佬代码

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]
           

大神一句话的事！省题很重要，题目中假设了每个数组都有众数。

求众数先排序，取中间值。