剑指 Offer 39. 数组中出现次数超过一半的数字
发布日期:2021-06-20 02:50:20 浏览次数:5 分类:技术文章

本文共 676 字,大约阅读时间需要 2 分钟。

题目

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

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

示例一

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

输出: 2

思路一

  • 找众数。用一个map<int, int>,前面存数字的数值,后面存出现的次数,这样可以统计出来出现了多少次。

需要开一个O(n)的空间,时间复杂度需要遍历整个数组。O(n)

思路二

  • 排序。排序结束后的数组的中间数字是众数。排序快的基本上是O(nlogn)的时间复杂度

思路三

  • 摩尔投票法。选一个candiadte,如果两个数字相同,票数++,否则票数–;当票数0时证明,前面这些数字可以去除。在下面的数组里面继续找众数。

代码

class Solution {
public: int majorityElement(vector
& nums) {
int n = nums.size(), candidate = nums[0], vote = 1; for(int i = 1;i < n;i++){
nums[i] != candidate ? vote-- : vote++; if(vote == 0 && i < n - 1) candidate = nums[i + 1]; // cout<
<<" "<
<<" "<
<

转载地址:https://blog.csdn.net/free1993/article/details/115077518 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:剑指 Offer 57 - II. 和为s的连续正数序列
下一篇:剑指 Offer 10- I. 斐波那契数列

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月09日 08时27分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

matlab转差频率控制,转差频率控制的异步电机调速系统的研究 2019-04-21
oracle错误1327,Oracle中的PGA监控报警分析(r11笔记第97天) 2019-04-21
php函数内的循环,PHP 循环列出目录内容的函数代码 2019-04-21
oracle树状排序,Oracle树状结构查询 2019-04-21
深度linux内核升级,深度操作系统 2020.11.11 更新发布:内核升级 2019-04-21
sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解) 2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类 2019-04-21
macbook pro 卸载mysql_MacBook Pro全新重装OS X Yosemite 2019-04-21
已达到计算机的连接数最大值无法再同此远程计算机连接_电脑远程访问已达到计算机的连接数最大值怎么办?解决方法很简单... 2019-04-21
mysql表名长度_JavaWeb之MySQL(一) 2019-04-21
mysql服务器语法_Mysql语法 2019-04-21
pdf 模版 汉字和数字_《吉林大学珠海学院毕业论文(设计)模板》(汉字标题版) .pdf... 2019-04-21
python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行 2019-04-21
redis logfile为空_关于Redis(二) 2019-04-21
mysql 设计两个主键都不可重复_程序员面试备战篇:18个经典MySQL面试专题解析(干货分享答案)... 2019-04-21
下列关于python2.x和3.x的区别说法正确_Python 2.x和Python 3.x版本有哪些区别?【面试题详解】... 2019-04-21
git更换_git命令 2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析 2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件 2019-04-21