PAT甲级1041.

目录

A1041

题目

样例

样例1

输入:

7 5 31 5 88 67 88 17

输出:

31

样例2

输入:

5 888 666 666 888 888

输出:

None

思路和坑点

　　使用两个映射记录数据，一个用于记录每个数字出现的个数，另一个用于记录备选答案以及其出现的次序，最后从备选答案中选出次序最小的也就是第一个出现的为最终答案。如果没有答案，则按照要求输出None

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    unordered_map<int,int> mp,mpout;        //mp用于计数，mpout用于备选输出答案，记录出现的次序 
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        mp[num]++;
        if(mp[num]==1)                        //如果只有一个则加入备选，，并记录次序 
            mpout[num]=i;
        else
            mpout.erase(num);                //如果不只有一个，则从被选中删除 
    }
    int win,min=n;                            //从备选的输出项中选出次序最小的，也就是第一次出现的答案 
    for(auto it=mpout.begin();it!=mpout.end();it++){
        if(it->second<min){
            win=it->first;
            min=it->second;
        }
    }
    if(mpout.size()==0) puts("None");        //如果最终没有答案，输出None 
    else cout<<win;
    return 0;    
}