题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，其中有一个数字的个数，超过整体的一半，求出这个数字是什么

思路分享

  • 哈希表查重的方法不多赘述，这里介绍灵神所教的一种方法，多数投票。

  • 意思就是，设置一个初始值，和初始计数 1，如果遇到的值与初始值相等，则计数加一，否则计数减一，一旦计数归零，下个数字就当作初始值，计数设为 1。由于答案的数字一定比其他数字都多，所以这个算法下来的最终值一定为答案。

    https://leetcode.cn/problems/majority-element/solutions/3744717/on-mo-er-tou-piao-fa-yan-jin-zheng-ming-ww1zv/

  • 但必须重申，这个算法的实现需要答案的个数严格大于整体个数的一半，不能只是一半。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans, hp = 0, 0
        for num in nums:
            if hp == 0:
                ans, hp = num, 1
            else:
                hp += 1 if num == ans else -1
        return ans