专栏首页vblogPAT 1041 Be Unique (20分)利用数组找出只出现一次的数字

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1023 Have Fun with Numbers (20分) 字符数组解决大整数存储溢出

    Notice that the number 123456789 is a 9-digit number consisting exactly the numb...

    vivi
  • PAT 1017 Queueing at Bank (25分) prioriry_queue

    Suppose a bank has K windows open for service. There is a yellow line in front o...

    vivi
  • PAT 1021 Deepest Root (25分) 从测试点3超时到满分再到代码优化

    A graph which is connected and acyclic can be considered a tree. The height of t...

    vivi
  • 干货 | 一文带你读懂DeepMind新论文,关联推理为什么是智能最重要的特征

    大数据文摘
  • PAT(乙级)1019

    分析:这个题目,没什么难度。但是我被超时问题困扰了一会儿,可能是scanf函数用的次数有点多,所以改了一下,直接通过了。

    zy010101
  • 探索 | 神经网络到底是如何思考的?MIT精英们做了这么一个实验室来搞清楚

    作者 | Larry Hardesty等 编译 | ziqi Zhang 没错!人工智能是很火,神经网络也很火,但你真的懂它吗?神经网络到底是怎么工作的?没有...

    AI科技大本营
  • LintCode-569.各位相加

    相加的过程如下:3 + 8 = 11,1 + 1 = 2。因为 2 只剩下一个数字,所以返回 2。

    悠扬前奏
  • 通过反汇编理解函数调用机制(x86和ARM)

    在分析上面的汇编程序之前,需要了解rbp、rsp为栈基址寄存器、栈顶寄存器,分别指向栈底和栈顶;edx、eax、esi、edi均为x86CPU上的通用寄存器,...

    用户7043923
  • Leetcode_342_Power of Four

    http://blog.csdn.net/pistolove/article/details/52198328

    bear_fish
  • 各位相加,直到得到一个一位的整数

    从1开始,结果依次是1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9····

    你好戴先生

扫码关注云+社区

领取腾讯云代金券