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

题目描述

https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

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

限制：

1 <= 数组长度 <= 50000

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

解题思路

1.排序法：
直接排序，取中间那个数。
2.摩尔投票法：
介绍参考：https://www.zhihu.com/question/49973163/answer/235921864
输入：{1,2,1,3,1,1,2,1,5}
从第一个数字1开始，我们想要把它和一个不是1的数字一起从数组里抵消掉，但是目前我们只扫描了一个1，所以暂时无法抵消它，把它加入到array，array变成了{1}，result由于没有抵消任何元素所以还是原数组{1,2,1,3,1,1,2,1,5}。
然后继续扫描第二个数，是2，我们可以把它和一个不是2的数字抵消掉了，因为我们之前扫描到一个1，所以array变成了{},result变成了{1,3,1,1,2,1,5}
继续扫描第三个数1，无法抵消，于是array变成了{1},result还是{1,3,1,1,2,1,5};
接下来扫描到3,可以将3和array数组里面的1抵消,于是array变成了{},result变成了{1,1,2,1,5}接下来扫描到1，此时array为空，所以无法抵消这个1，array变成了{1},result还是{1,1,2,1,5}
接下来扫描到1，此时虽然array不为空，但是array里也是1，所以还是无法抵消，把它也加入这个array,于是array变成了{1,1}（其实到这我们可以发现，array里面只可能同时存在一种数，因为只有array为空或当前扫描到的数和array里的数字相同时才把这个数字放入array）,result还是{1,1,2,1,5}
接下来扫描到2，把它和一个1抵消掉，至于抵消哪一个1，无所谓，array变成了{1},result是{1,1,5}
接下来扫描到1，不能抵消，array变成了{1,1}，result{1,1,5}
接下来扫描到5，可以将5和一个1抵消，array变成了{1},result变成了{1}
至此扫描完成了数组里的所有数，result里剩了1，所以1就是大于一半的数组。
我们用栈来实现result数组，最后pop(stack)出来的就是想要的数。

解题代码

排序法：

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

摩尔投票法：

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        stack = []
        for i in range(0, len(nums)):
            if stack == []:
                stack.append(nums[i])
            else:
                if nums[i] != stack[-1]:
                    stack.pop()
                else:
                    stack.append(nums[i])
        return stack.pop()

执行结果

排序法：40ms 15.9MB
摩尔投票法：56ms 16MB