Leetcode 169. Majority Element

Question

Solution1

考虑用字典来解。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dict = {}
        for num in nums:
            if num not in dict:
                dict[num] = 1
            else:
                dict[num] += 1
        return list(dict.keys())[list(dict.values()).index(max(dict.values()))]

因为题目中限定majority的次数大于n/2， 即只有一个majority，所以当其次数大于n/2时，直接跳出循环

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dict = {}
        for num in nums:
            if num not in dict:
                dict[num] = 1
            if dict[num] > len(nums)//2:
            	return num
            else:
                dict[num] += 1

Solution2

因为题目中说，majority的次数大于n/2，所以直接排序返回中间的就行。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums)//2]