题解 | #数组中出现次数超过一半的数字#的Python解法

1. 解题思路之了解暴力法

题目的描述这句话（“例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。”）其实就已经给出了思路。就是👉暴力解法：

首先找到数组长度的一半，这里为 $图片说明$ ，定为 n 变量；
接着统计数组中各个数字的出现次数为count变量；
最后比较n 和count 的大小，仅当count > n时，才返回对应的数字。

2. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return None
        while numbers:
            #首先找到数组的一半长度大小
            n = len(numbers) // 2
            #接着统计数组中每个数字的出现次数
            for i in numbers:
                count = sum(1 for j in numbers if j == i)
                #比较统计后的每个数字的次数 与 n的大小，只有超过二分之一数组长度的才是我们要找的数字
                if count > n:
                    return i

❗❗❗暴力解法虽然思路很简单，但是会超时。。。所以不可取❌
图片说明

所以这里我们优化一下，采用哈希的正确解法！ ✅

3. 正确解法一：哈希表

3.1 思路

思路与暴力类似，但是最后直接返回哈希表中最大值对应的key即可。看图解示例1会更形象的理解：
图片说明

3.2 核心代码

# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return None
        #首先找到数组的一半长度大小
        n = len(numbers) // 2
        #接着统计数组中每个数字的出现次数
        count = Counter(numbers)
        #返回次数最大的对应key即所求
        return max(count.keys(), key=count.get)

3.3 复杂度分析

时间复杂度： $O(n)$ (n为数组的长度，只需要遍历一次数组并插入到哈希表中)
空间复杂度： $O(n)$ (因为哈希表最多有 $图片说明$ 个键值对，所以占用空间为O(n))

--------------------------------------------我是解法二的分割线------------------------------------------------

4. 解法二

4.1 思路

除了哈希表解法外，这里我们还可以采用 排序法 来解此题。具体思路图解如下：
图片说明

4.2 核心代码

# -*- coding:utf-8 -*-
from collections import Counter
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers == []:
            return None
        #对数组排序
        numbers.sort()
        #返回中间位置所在数字即所求
        return numbers[len(numbers)//2]

4.3 复杂度分析

时间复杂度： $O(nlogn)$ (数组排序的时间复杂度为 $O(nlogn)$ )
空间复杂度： $O(logn)$ (排序算法需要 $O(logn)$ 的栈空间)

--------------------------------------------我是解法三的分割线------------------------------------------------

5. 解法三：摩尔投票算法（Boyer–Moore majority vote algorithm）

5.1 思路

首先我们来了解一下摩尔投票算法的一些基础知识。

概念：指通过线性的时间和固定的空间来找到一组序列中众数是哪一个的一种算法。
具体步骤：
- 首先创建一个初始指针，从序列一开始位置扫描；同时这个指针扫描的对象包含： a current candidate（一个当前的候选人）和a counter（当前候选人的票数）。当然一开始这个候选人是未知的；票数也就是0。
- 接着移动指针经过每个元素：
  - 如果一开始的票数为0，那么就把当前元素作为candidate，并且票数变为1；
  - 如果票数不为0，那么就根据该元素是否与candidate相同，相同则票数＋1；否则票数减1。 当票数减为0 后，又开始寻找新的candidate并统计票数，重复前面的步骤。
- 直到指针走完整个序列，如果序列存在众数，那么当前的candidate就是我们要找的众数。

接下来看本题，本题要找数组中出现次数超过一半的数字，且题目告诉我们👉给定的数组总是存在多数元素👈其实是变相告诉我们，“众数”是存在于这个数组中的！ 所以这里我们也可以采用摩尔投票算法的思路来解，下面看本题摩尔算法的图解示例1：
图片说明

5.2 核心代码

# -*- coding:utf-8 -*-

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        counts = 0             #定义初始票数为0
        candidate = None       #初始候选人为None
        for i in numbers:      #接下来利用摩尔投票遍历数组
            if counts == 0:     #首先初始元素就是当前候选人，所以票数自然+1
                candidate = i
            counts += (1 if i == candidate else -1)  #接下来比较候选人是否相同，相同候选人就+1；不同就-1
        return candidate

5.3 复杂度分析

时间复杂度： $O(n)$ (摩尔投票算法只需要对数组进行一次遍历即可，数组长度为n，所以时间复杂度为 $O(n)$ )
空间复杂度： $O(1)$ (摩尔投票算法不涉及额外空间的使用)