剑指 Offer 39. 数组中出现次数超过一半的数字

难度简单164收藏分享切换为英文接收动态反馈

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

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

示例 1:

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

限制：

1 <= 数组长度 <= 50000

注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/

169. 多数元素

难度简单1021收藏分享切换为英文接收动态反馈

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

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

示例 1：

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

示例 2：

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

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题目解析

哈希表统计法

顾名思义，就是将所有变量进行利用哈希表存储，然后逐个统计个数，时间和空间都需要$$O(N)$$

数组顺序法

该方法则取决于排序的方法的时间和空间复杂度

摩尔投票法

利用票数正负抵消的思想进而实现找寻变量的功能。

算法解析

记超过半数的变量为+1，其他变量为-1，全部变量总和>0
当数组的前a个数字之和=0，剩余的数字之和>0,即在子数组中该变量依旧满足超过半数的要求；

基于以上推论，可以利用和=0可缩小寻找范围的特性，实现算法

假设首元素为n，寻找变量为x，当现在前a个数字票数和=0，此时

n=x时，说明当前一半是x，并实现了抵消
$n \neq x$时，说明当前数字实现了抵消，剩余的数组中x依旧满足超过半数

算法流程

初始化

# 统计计数
vote = 0

循环遍历

for num in nums:
    if vote == 0:x = num
    vote += 1 if num==x else -1
return x

通过代码

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