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 1731,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;
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://vivi.run/archives/pat-1041-be-unique-20