mode（思维，注意内存）-白红宇

mode（思维，注意内存）

阅读量：6234 次

发布时间：2019-06-22

本文共 1327 字，大约阅读时间需要 4 分钟。

mode

Time Limit:1000MS Memory Limit:1024KB 64bit IO Format:%lld & %llu

Description

给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。

Input

第1行一个正整数n。第2行n个正整数用空格隔开。

Output

一行一个正整数表示那个众数。

Sample Input

5 3 2 3 1 3

Sample Output

Hint

100%的数据，n<=500000，数列中每个数<=maxlongint。

题解：

注意这个题，对内存要求非常高1024k，1kb等于1024字节，如果想用数组的话，至少要500000*4/1024大概要2000k，还不算原本程序什么的占的内存；原来我还想着用map记录的，因为想到数据不超过int也呆1e9多，那肯定报内存，现在想想map也会爆内存，怎么办呐，我们只有用数字代替了，因为数字出现的个数会是n的一半还多，那么我们只需要每一步，如果跟上一个相等就++不想等就等于当前，因为ans必然会出现n的一半还多，所以不愁得不到答案了；

代码：

/*#include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 using namespace std;typedef long long LL;map
                 
                  mp;int main(){ char s[20]; char ans[20]; int n; while(~scanf("%d",&n)){ mp.clear(); for(int i=0;i
                  
                   n/2)strcpy(ans,s); } puts(ans); } return 0;}*/#include
                   
                    #include
                    
                     /*int cmp(const void *a,const void *b){ return *(int *)a<*(int *)b;}int a[500005];int main(){ int n; while(~scanf("%d",&n)){ for(int i=0;i
                     
                      n/2)ans=a[i-1]; cur=1; } } if(cur>n/2)ans=a[n-1]; printf("%d\n",ans); } return 0;}*/int n,ans,cur,num;int main(){ while(~scanf("%d",&n)){ ans=-1;num=0; while(n--){ scanf("%d",&cur); if(cur==ans)num++; else{ num--; if(num<0){ ans=cur; num=1; } } } printf("%d\n",ans); } return 0;}

转载地址：http://qgqna.baihongyu.com/

你可能感兴趣的文章