剑指 Offer 39. 数组中出现次数超过一半的数字 - leetcode 剑指offer系列
发布日期:2021-06-29 07:12:15
浏览次数:4
分类:技术文章
本文共 1417 字,大约阅读时间需要 4 分钟。
题目难度: 简单
今天继续更新剑指 offer 系列, 这道题估计大家或多或少都见过, 这里就来复习下做法吧, 重点是要理解为什么这样做是可行的
老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
1 <= 数组长度 <= 50000
题目样例
示例
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2题目思考
- 如何不使用额外空间?
- 如果题目不保证一定存在多数元素又该怎么办?
解决方案
思路
- 一个最简单的思路是用一个计数字典存每个数字的出现次数, 找最大的那个即可, 但这需要额外的空间, 不是面试官心目中的理想答案
- 重新分析题目, 某个数字出现超过一半, 那意味着其他数字的数目之和都小于它, 如果我们将这些不同数字进行两两抵消, 那么最后剩余的那个数字一定是超过一半的那个数字, 这就引出了下面的思路:
- 维护一个当前候选者, 以及当前它的计数, 初始化就是数组头一个数字, 计数为 1
- 从第二个数字开始遍历数组, 如果当前数字等于候选者, 那么计数值加 1, 否则就减 1 表示抵消了一个数字
- 如果此时计数小于 0 的话, 就说明之前的候选者这个时候要被淘汰了, 因为它已经被抵消光了. 所以就重新选择当前的数字作为新的候选者, 同时重置计数值为 1.
- 这样最后剩余的那个候选者一定是最终结果, 因为此题的前提是一定存在这样的数字
- 当然, 如果题目不保证一定存在多数元素, 那么我们在得到最终候选者之后, 需要重新遍历一遍数组并累加其计数, 确保其计数超过一半, 不然的话就说明整个数组没有多数元素. 例如数组
[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
大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
转载地址:https://blog.csdn.net/zjulyx1993/article/details/107569405 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月12日 15时15分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C语言指针,这可能是史上最干最全的讲解啦(附代码)!!!
2019-04-29
国内大陆有哪些芯片公司处于世界前10?一起看看!
2019-04-29
单精度、双精度、多精度和混合精度计算的区别是什么?
2019-04-29
中国35位“大国工匠”榜单出炉!西工大、西电合计占半壁江山!清华仅1人!...
2019-04-29
知乎热议:嵌入式开发中C++好用吗?
2019-04-29
2020,Python 已死?
2019-04-29
漫画:程序员相亲?哈哈哈哈哈哈
2019-04-29
30种EMC标准电路分享,再不收藏就晚了!
2019-04-29
这100道Linux常见面试题,看看你会多少?
2019-04-29
十年硬件老司机,结合实际案例,带你探索单片机低功耗设计!
2019-04-29
“2020年嵌入式软件秋招经验和对嵌入式软件未来的一点思考”
2019-04-29
嵌入式的坑在哪方面?
2019-04-29
三种常见嵌入式设备通信协议
2019-04-29
硬核,这个充电宝居然烧煤气!
2019-04-29
什么是模块化代码?如何写?
2019-04-29
STM32串口发送数据和接收数据方式总结
2019-04-29
来,看看这20个常用的宏定义!
2019-04-29
嵌入式开发中常用的几种通信接口总结
2019-04-29
为什么我那么努力,模电还是学不懂?
2019-04-29
PID系统稳定性与零极点的关系
2019-04-29