面试题39. 数组中出现次数超过一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：
1 <= 数组长度 <= 50000

答案1

from typing import List
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res = sorted(nums)[len(nums) // 2]
        return res
Solution().majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2])

Note

先排序，中位数就是大于一般的那个数

答案2

from typing import List
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        card = 0
        t = 0
        for i in nums:
            if count == 0: card = i
            if card == i:
                t = 1
            else:
                t = -1
            count += t
        print(card)
        return card

Note

摩尔投票法