剑指 Offer 39. 数组中出现次数超过一半的数字 - leetcode 剑指offer系列

题目难度: 简单

原题链接

今天继续更新剑指 offer 系列, 这道题估计大家或多或少都见过, 这里就来复习下做法吧, 重点是要理解为什么这样做是可行的

老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

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

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

1 <= 数组长度 <= 50000

题目样例

示例

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

题目思考

1. 如何不使用额外空间?
2. 如果题目不保证一定存在多数元素又该怎么办?

解决方案

思路

• 一个最简单的思路是用一个计数字典存每个数字的出现次数, 找最大的那个即可, 但这需要额外的空间, 不是面试官心目中的理想答案
• 重新分析题目, 某个数字出现超过一半, 那意味着其他数字的数目之和都小于它, 如果我们将这些不同数字进行两两抵消, 那么最后剩余的那个数字一定是超过一半的那个数字, 这就引出了下面的思路:
  1. 维护一个当前候选者, 以及当前它的计数, 初始化就是数组头一个数字, 计数为 1
  2. 从第二个数字开始遍历数组, 如果当前数字等于候选者, 那么计数值加 1, 否则就减 1 表示抵消了一个数字
  3. 如果此时计数小于 0 的话, 就说明之前的候选者这个时候要被淘汰了, 因为它已经被抵消光了. 所以就重新选择当前的数字作为新的候选者, 同时重置计数值为 1.
  4. 这样最后剩余的那个候选者一定是最终结果, 因为此题的前提是一定存在这样的数字
• 当然, 如果题目不保证一定存在多数元素, 那么我们在得到最终候选者之后, 需要重新遍历一遍数组并累加其计数, 确保其计数超过一半, 不然的话就说明整个数组没有多数元素. 例如数组[1,2,3], 利用此方法得到的最终候选者为 3, 但它并不是多数元素, 只是恰好最后一个被选出来的候选者而已.

复杂度

• 时间复杂度 O(N)
  • 只需要遍历数组一遍
• 空间复杂度 O(1)
  • 只使用了几个变量

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # 初始化候选者和计数
        res = nums[0]
        cnt = 1
        for x in nums[1:]:
            if x == res:
                # 当前元素等于候选者, 计数值+1
                cnt += 1
            else:
                # 否则计数值-1
                cnt -= 1
                if cnt < 0:
                    # 如果计数值小于0的话, 就说明之前保存的候选者现在被淘汰了, 将当前元素变为新的候选者, 并重置计数值为1
                    res = x
                    cnt = 1
        return res

大家可以在下面这些地方找到我~????

我的知乎专栏

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~????

最后

以上就是机智钻石为你收集整理的剑指 Offer 39. 数组中出现次数超过一半的数字 - leetcode 剑指offer系列的全部内容，希望文章能够帮你解决剑指 Offer 39. 数组中出现次数超过一半的数字 - leetcode 剑指offer系列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。