PAT 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,10​4 ]. 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 (≤10​5​​ ) 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:

31

Sample Input 2:

5 888 666 666 888 888

Sample Output 2:

None

题目解读

给出N个正整数，找出第一个只出现了一次的数字，比如 5 31 5 88 67 88 17，31，67，17都只出现了一次，但是31是第一个，所以输出31；如果没有唯一的数字，输出 None。

思路很简单：利用一个整型数组统计每个数字出现的次数，找出第一个次数为1的数字并输出。

因为这些数字本身在输入中是无序的，因此不能直接用数字做下标，次数做值，这样会导致结果错误，比如上面那个例子 5 31 5 88 67 88 17，若用数字本身做下标，17会排在前面，最后会输出17.

因此设计两个数组，num[]保存出现按顺序的这些数字，count[]保存这些数字出现的次数，最后只需要这样遍历：

    // 判断第一个只出现了一次的数字
    for(int i = 0; i < n; i++) {
        if(count[num[i]] == 1) {
            printf("%d", num[i]);
            return 0;
        }
    }

num[]本身按顺序读取输入并存储保证了数字的有序性。

完整代码

#include <cstdio>
using namespace std;

int num[100000], count[100000];

int main() {
    int n;
    scanf("%d", &n);
    int x;
    for(int i = 0; i < n; i++) {
        // 当前数字
        scanf("%d", &num[i]);
        // 当前数字出现的次数
        count[num[i]]++;
    }
    // 判断第一个只出现了一次的数字
    for(int i = 0; i < n; i++) {
        if(count[num[i]] == 1) {
            printf("%d", num[i]);
            return 0;
        }
    }
    // 都重复，输出 None
    printf("None");
    return 0;
}