169 - 多数元素 - python

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

---

题目要求返回出现次数大于⌊ n/2 ⌋ 的元素，这里需要使用ceil()进行向下取整，并使用Counter()统计数组中元素及其出现的次数，最后遍历统计字典中元素的值，找到值大于⌊ n/2 ⌋ 的键返回即可。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums: return 0

        l = ceil(len(nums) // 2)
        d = Counter(nums)      
        for k, v in d.items():
            if v > l:
                return k
        return 0

另外在题解中还看到两种有意思的方法，一种是随机法：因为所属元素的个数要大于 ⌊ n/2 ⌋ ，那么表示数组中超过一半的元素都是最后要找的元素，那么随机选择一个元素就是要求的数的概率也就大于0.5.因此，可以采用随机取数判断的方法解决。

import random

class Solution:
    def majorityElement(self, nums):
        majority_count = len(nums)//2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

还有一种第一次见到的摩尔投票法，详细题解可见江不知 - 图解摩尔投票法（Python & Go）

class Solution(object):
    def majorityElement(self, nums):
        major = 0
        count = 0
        
        for n in nums:
            if count == 0:
                major = n
            if n == major:
                count = count + 1
            else:
                count = count - 1

        return major