1041 Be Unique (20 分) PAT 甲级散列

布满荆棘的人生 2024-02-19 21:43 50阅读 0赞

## 1041 Be Unique (20 分) ##

Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from \[1,104\]. The first one who bets on a unique number wins. For example, if there are 7 people betting on \{ 5 31 5 88 67 88 17 \}, then the second one who bets on 31 wins.

#### Input Specification: ####

Each input file contains one test case. Each case contains a line which begins with a positive integer N (≤105) and then followed by N bets. The numbers are separated by a space.

#### Output Specification: ####

For each test case, print the winning number in a line. If there is no winner, print `None` instead.

#### Sample Input 1: ####

7 5 31 5 88 67 88 17

#### Sample Output 1: ####

#### Sample Input 2: ####

5 888 666 666 888 888

#### Sample Output 2: ####

None

思路：

我用了两个map

一个存次序，另外一个存出现的次数。

#include<iostream>
    #include<map>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int n,i,j=1,t,f=0;
    	map<int,int> a;    //用来统计出现的次数 
    	map<int,int> b;    //拍顺序 
    	b.clear();
    	a.clear();
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    		cin>>t;
    		if(a.count(t)==0)
    		{
    			a.insert(make_pair(t,1));
    			b.insert(make_pair(j++,t));
    		}
    		else
    		a[t]++;
    	}
    	for(map<int,int>::iterator it=b.begin();it!=b.end();it++)
    	{
    		if(a[it->second]==1)
    		{
    			cout<<it->second<<endl;
    			f=1;
    			break;
    		}
    	}
    	if(f==0)
    	cout<<"None"<<endl;
    	return 0;
    }

别人的代码：

#include<cstdio>
    const int maxn=1e5+10;
    int book[maxn]={0} ;
    int a[maxn];
    int main(){
        int n,x;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            a[i]=x;
            book[x]++;
        }
        int ans=-1;
        for(int i=0;i<n;i++){
            if(book[a[i]]==1){
                ans=a[i];
                break;
            }
        }
        if(ans==-1) printf("None\n");
        else printf("%d\n",ans);
        return 0;
    }