169.majority-element.md

题目地址

https://leetcode-cn.com/problems/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.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

思路

方法一：

• 统计每个字母出现的次数
• 选出次数出现最多的字母

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d = {}
        for i in nums:
            if d.get(i) != None:
                d[i] += 1
            else:
                d[i] = 0
        return max(d, key=d.get)

以下方法为看题解得知更简便的方法
方法二 中位数

• 由于题目中已知出现次数最多的数字个数必定大于n/2的下限，那么该数字必定是中位数。
• 排序并返回中位数即可。

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

方法三：随机法
由于所求的数字出现次数超过一半，那么随机抽选出一个进行比较

import random
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums) // 2
        while True:
            r = random.choice(nums)
            if sum(1 for elem in nums if r == elem) > n:
                return r

方法四：Boyer-Moore 投票算法
将众数记为+1，其他的记为-1，将他们加起来，显然和大于0。 如果票选出来的不是众数candidate，那么candidate作为众数则可以推翻票选人。 如果票选出来的是众数candidate，即使其他数字反对，也无法超过candidate的数量，反对无效。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if candidate == num else -1)
        return candidate