当前位置：首页 > news >正文

mode（思维，注意内存）

news 来源：原创 2024/5/17 21:56:01

mode

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

Submit Status Practice HYSBZ 2456

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<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<string>
using namespace std;
typedef long long LL;
map<string,int>mp;
int main(){
    char s[20];
    char ans[20];
    int n;
    while(~scanf("%d",&n)){
        mp.clear();
        
        for(int i=0;i<n;i++){
            scanf("%s",s);
            mp[s]++;
            if(mp[s]>n/2)strcpy(ans,s);
        }
        puts(ans);
    }
    return 0;
}
*/
#include<stdio.h>
#include<stdlib.h>
/*
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;i++)scanf("%d",a+i);
        qsort(a,n,sizeof(a[0]),cmp);
        int cur=1,ans;
        for(int i=1;i<n;i++){
            if(a[i]==a[i-1])cur++;
            else{
                if(cur>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;
}