刷无悔 169 ～ 主要元素

基本信息

• 题号：169
• 题厂：脸书
• 难度系数：低

数组里面有一个数出现次数是数组长度一半以上，即数组主要元素。

问：把主要元素找出来……

例如：nums = [3,2,3]

3 是主要元素，返回 3

解题思路

• 计算出现次数这种事，一般都靠 hashmap 辅助。
• 本题如果靠 hashmap，当 count 计数超过一半时就返回。
• 一半上限，即 数组长度 / 2

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        half = len(nums) // 2
        counter = {}
        
        for num in nums:
            counter[num] = 1 + counter.get(num, 0)
            
            if counter[num] > half:
                return num

靠以上 hashmap 计数的解法，我们在 5 分钟内击败了 85% 的解法，然而本题还有后续🐮：

如何使用 O（1）的空间利用率解决问题？？？！！！

如果要用 O（1）解决空间利用率，意味着 hashmap 这种数据结构无法登场。所以请出了超高级的人名算法——Boyer-Moore 🤪

题目确定了已知数组一定有主要元素（出现次数超过一半），[2,1,3] 这种无主要元素的状况不会出现，于是引用 Boyer-Moore 解题。简单理解就是：

• 如果当前计数器为 0， 就初始化返回值为当前元素；
• 如果当前元素和返回值相等，计数器 +1；
• 如果当前元素和返回值不等，计数器 -1；
• 因为主要元素出现次数超过一半，能把计数器清零后在获得重置权的肯定就只有主要元素了……所以这样一来，当 for 循环遍历完成后，返回值一定就是当前数组主要元素😵

Constraints

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

考试时可以向考官确认主要元素到底存不存在，需不需要考虑不存在情况🙈

Big O

• Time：O（n）
• Space：引入 hashmap 为 O（n）；Boyer-Moore 最优解为 O（1）

测试

• 数组为 1 时
• 主要元素插空出现
• 主要元素在开头出现
• 主要元素在末尾出现
• 次要元素有一个多个值
• ……

总结

• 本题如果就是 hashmap 计数，这是一道 10 分钟内即可搞定的简单题；
• 最优解法 Boyer-Moore 虽然代码依然简单，但算法小白是一定不可能想出来的，所以最优解甚至可以归为难挡😭
• 考试时当你第一时间完成了 hashmap 解法后，考官一定还会问你有没有其他解法，优化解法（此处即算法小白几乎不可能想出的 Boyer-Moore）……😭

更多Boyer-Moore 强大介绍 🙈：

https://www.geeksforgeeks.org/boyer-moore-majority-voting-algorithm/