剑指 Offer 39. 数组中出现次数超过一半的数字（摩尔投票法/哈希表）

• 题目描述

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

 

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

 

示例 1:

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

• 解法一：摩尔投票法

新学一个方法，我们首先了解下摩尔投票法是怎么个过程，此部分参考大佬的知乎链接：https://www.zhihu.com/people/mo-jian-chen-63

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

输入：{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就是大于一半的数组。

再回顾一下这个过程，其实就是删除（抵消）了（1，2），（1，3），（1，5）剩下了一个1。

代码怎么实现呢？

major 初始化随便一个数，

count 初始化为0

输入：{1,2,1,3,1,1,2,1,5}

• 扫描到1，count是0（没有元素可以和当前的1抵消），于是major = 1，count = 1（此时有1个1无法被抵消）
• 扫描到2，它不等于major，于是可以抵消掉一个major => count -= 1，此时count = 0,其实可以理解为扫到的元素都抵消完了，这里可以暂时不改变major的值
• 扫描到1，它等于major，于是count += 1 => count = 1
• 扫描到3，它不等于major，可以抵消一个major => count -= 1 => count = 0，此时又抵消完了(实际的直觉告诉我们，扫描完前四个数，1和2抵消了，1和3抵消了)
• 扫描到1，它等于major，于是count += 1 => count = 1
• 扫描到1，他等于major，无法抵消 => count += 1 => count = 2 (扫描完前六个数，剩两个1无法抵消)
• 扫描到2，它不等于major，可以抵消一个major => count -= 1 => count = 1,此时还剩1个1没有被抵消
• 扫描到1，它等于major，无法抵消 => count += 1 => count = 2
• 扫描到5，它不等于major，可以抵消一个major => count -= 1 => count = 1

至此扫描完成，还剩1个1没有被抵消掉，它就是我们要找的数。

那这道题就可以这样解了（自己写的，代码有点冗余）：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        '''
        摩根投票法
        '''
        target = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if nums[i] != target and count != 0:
                count -= 1
            elif nums[i] != target and count ==0:
                target = nums[i]
                count += 1
            elif nums[i] == target:
                count += 1
        return target

时间复杂度O(N)

空间复杂度O(1)

看看大佬的：

票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1，非众数 的票数为 -1 ，则一定有所有数字的 票数和 >0 。
票数正负抵消： 设数组 nums 中的众数为 x，数组长度为 n。若 nums 的前 a 个数字的 票数和 =0 ，则 数组后 (n-a)个数字的 票数和一定仍 >0>0 （即后 (n−a) 个数字的 众数仍为 x ）。

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

时间复杂度O(N),

空间复杂度O(1)

参考：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/

• 解法二：hash表

用hash表存储每个元素出现的次数，如果出现次数大于长度的一半则判断找到这个元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hash_map = {}
        for i in range(len(nums)):
            if nums[i] not in hash_map:
                hash_map[nums[i]] = 1
            else:
                hash_map[nums[i]] += 1
            if hash_map[nums[i]] > len(nums) //2:
                return nums[i]

时间复杂度O(N)  

空间复杂度O(N)