「求衆數」| 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]
           

大神一句話的事！省題很重要，題目中假設了每個數組都有衆數。

求衆數先排序，取中間值。