数组中出现次数超过一半的数字（摩尔投票）

问题简述

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

详细描述

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

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

示例 1:
    输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2
限制：
    1 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：排序

• 排序后，数组中间位置的数一定满足题意；

• 时间复杂度 O(NlogN)；

Python

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

思路2：计数

• 一次遍历，记录每个数出现的次数；

• 空间复杂度 O(N)；

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import defaultdict

        cnt = defaultdict(int)

        for x in nums:
            cnt[x] += 1
            if cnt[x] > len(nums) // 2:
                return x
        
        # return -1

思路3：“摩尔投票法”

数组中出现次数超过一半的数字（摩尔投票法，清晰图解）

• “摩尔投票法”的核心思想是一一抵消；

• 假设已知目标数为 x，遍历时若出现一次 x 记 +1 票，否则为 -1 票；

  • 推论1：最终票数和必大于 0；

  • 推论2：若前 n 个数的票数和为 0，那么剩余部分依然满足推论1，即目标数字依然为 x；

Python

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

        cnt = 0
        for x in nums:
            if cnt == 0:  # 当票数和为 0 时，假设当前值为目标值
                ret = x   # 如果这个数不是目标值，那么它迟早会因为不断 -1，被替换掉
                
            if x == ret:
                cnt += 1
            else:
                cnt -= 1
        
        return ret

思路4：分治

数组中出现次数超过一半的数字

• 本题使用分治在时间和空间上都不是最优，仅用于理解分治的思想；

Python

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

        def recur(lo, hi):  # [lo, hi] 闭区间
            if lo == hi:  # 当数组中只有一个元素时，这个数就是目标值
                return nums[lo]

            # 分治
            mid = (hi - lo) // 2 + lo
            l = recur(lo, mid)
            r = recur(mid + 1, hi)

            # 如果左右返回值相同时，显然这个值就是目标值
            if l == r:
                return l

            # 否则需要判断哪个出现的次数更多
            lc = sum(1 for i in range(lo, hi + 1) if nums[i] == l)
            rc = sum(1 for i in range(lo, hi + 1) if nums[i] == r)
            return l if lc > rc else r

        return recur(0, len(nums) - 1)