LeetCode 169. Majority Element

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

分析

找出数组中的众数（出现次数大于数组长度一半）

代码

class Solution(object):
    # one pass + dictionary
    def majorityElement(self, nums):
        dic = {}
        for num in nums:
            if num not in dic:
                dic[num] = 1
            if dic[num] > len(nums)//2:
                return num
            else:
                dic[num] += 1 
    
    # two pass + dictionary
    def majorityElement1(self, nums):
        dic = {}
        for num in nums:
            dic[num] = dic.get(num, 0) + 1
        for num in nums:
            if dic[num] > len(nums)//2:
                return num
    
    # Divide and Conquer
    def majorityElement2(self, nums):
        if not nums:
            return None
        if len(nums) == 1:
            return nums[0]
        a = self.majorityElement(nums[:len(nums)//2])
        b = self.majorityElement(nums[len(nums)//2:])
        if a == b:
            return a
        return [b, a][nums.count(a) > len(nums)//2]
                
    def majorityElement3(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[len(nums)/2]

点评

一遍扫描+字典的做法，很容易理解，每次扫描的时候对出现的数 +1，然后判断是否大于 1