[LeetCode]169,229-求众数

169. 求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例:
输入: [3,2,3] -> 输出: 3
输入: [2,2,1,1,1,2,2] -> 输出: 2

解法1

基本思路, 用字典统计每个数的出现频率, 出现次数大于 n/2 的元素.

class Solution:
    def majorityElement(self, nums):
        dic = {}    # 用于记录每个元素的出现次数
        if len(nums) == 1:
            return nums[0]
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[nums[i]] = 1
            else:
                dic[nums[i]] += 1
                if dic[nums[i]] > len(nums)//2:
                    return nums[i]

解法2

思路: 快速解法, 先给数组排序, 如果有出现超过 n/2 次数的元素, 必然会出现在中间位置.

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[(len(nums) // 2)]

229. 求众数 II
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例:
输入: [1,1,1,3,3,2,2,2] -> 输出: [1,2]

解法1

思路和上一题解法1相同.

class Solution:
    def majorityElement(self, nums):
        dic = {}
        for i in range(len(nums)):
            if nums[i] not in dic:
                dic[nums[i]] = 1
            else:
                dic[nums[i]] += 1
        res = []    
        for num in dic:
            if dic[num] > len(nums)//3:
                res.append(num)
        return res

解法2

利用collections库里的counter

class Solution:
    def majorityElement(self, nums):
        return [i[0] for i in collections.Counter(nums).items() if i[1] > len(nums) / 3]