数组中出现次数超过一半的数字

发布时间:2017-3-20 6:51:14编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数组中出现次数超过一半的数字 ",主要涉及到数组中出现次数超过一半的数字 方面的内容,对于数组中出现次数超过一半的数字 感兴趣的同学可以参考一下。

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

代码

class Solution {public:    //有数字出现的次数超过数组长度的一半,说明该数字的个数会大于其它数字个数的和    //所以维护一个候选数以及候选数的个数,如果候选数的个数为0时(说明前面的数肯定是一半是相同的,两两抵消),当前数变更为候选数,重新计数为1。    int MoreThanHalfNum_Solution(vector<int> numbers) {        int c = 0 , cnt = 0;        for (auto num : numbers) {            if (cnt == 0) {                c = num;                cnt = 1;            } else {                c == num ? ++cnt : --cnt;            }        }        cnt = 0;        for (auto num : numbers) {            if (num == c) {                ++cnt;            }        }        return (cnt << 1) > (numbers.size()) ? c : 0;    }


上一篇:Apache Tika
下一篇:iOS for 和 forin 的区别 以及注意事项

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款