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

题目

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

 

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

 

示例 1:

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

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

题解思路

1>源代码

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

2>算法介绍

​本题的最佳解法是利用摩尔投票法，其核心思路是，假设将众数的票数定为1，非众数的票数定为-1，那么整个数组所有的票数和应该>0.

如果对于数组的前k个数来说，他们的票数和为0，那么意味着后面的n-k个数的票数和仍然应该>0，也就是说后面n-k个数的众数不变。

于是我们构造如上代码。