前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >寻找大小为n的数组中出现次数超过n/2的那个数

寻找大小为n的数组中出现次数超过n/2的那个数

作者头像
用户4415180
发布2022-06-23 14:09:29
5610
发布2022-06-23 14:09:29
举报
文章被收录于专栏:高并发

       问题描述: 在一个大小为n的数组中,其中有一个数出现的次数超过n/2,求出这个数。这题看似很简单,但是找到最优解不容易,一般情况我们首先想到最笨的方法,每选一个数,遍历一次数组,复杂度O(N^2),或者先排序再找那个数,复杂度一般为O(NlgN),或者用hash,时间复杂度O(N),空间复杂度需要看输入的数据规模,空间复杂度O(N)。所以这些都不是最优解,我们先分析一下这个题目,设该数出现的次数为x,则x满足,n/2+1<= x <=n;所以我们可以想到如果该数和其余的数全部相抵消的话,至少还剩1个,我们从前往后遍历,设key为第一个数,key出现的次数为ntime,初始化为1,代表key出现了一次,从前往后,如果某个数不等于key,则他俩抵消,key的出现次数减一,如果等于key,则key的出现次数加1,如果key的出现次数变成了0,则说明key已经用完了,所以需要重新初始化key为另一个数,再重复以上步骤,因为一定有一个数大于n/2,所以遍历到最后剩下的那个数,就是要求的数。

代码语言:javascript
复制
#include <iostream>
#include <vector>
using namespace std;
/*在大小为n的数组中寻找次数超过n/2的数*/
int find_data(vector<int> &arry)
{
    int ntime = 0; //表示其中某一个数出现的次数
    int result;
    for(unsigned int i = 0; i < arry.size(); i++) {
        if(ntime == 0) {   //在i前面的数全部删除完,或者起始的时候,将arry[i]放入结果
              result = arry[i];
              ntime = 1;  //arry[i]出现的次数为1;
        } else { //如果前面有数,就说明result还没抵消完
              if(result == arry[i]) //如果相等result出现的次数+1
                ntime++;
              else
                ntime--;  /*如果此时的arry[i]不等于result,则它们两个抵消,result的次数减一,由与那个数大于n/2所以它抵消不完,ntime最小为1
                            也就是说这个数出现的次数是大于等于n/2+1*/
        }
    }
    return result;
}
int main()
{
    vector<int> arry; 
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) {
            int d;
        cin>>d;
        arry.push_back(d);
    }
    int result = find_data(arry);
    cout<<result;
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-03-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档