PAT 解题报告 1041. Be Unique (20)

1041. Be Unique 题目描述:

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.

题目要求给出一组数字, 返回这些数字里面第一个没有重复出现过的数字, 也就是说第一个唯一出现一次的数字, 要是不存在这样的数字输出”None”.

1041. Be Unique 算法分析:

直接模拟, 线性扫一遍输入的所有数, 利用一个数组计数每个数值出现的次数, 然后再从头开始扫原数组, 直到碰到第一个唯一出现一次的数值, 输出即可. 代码见下面的, 给出了三段代码, 基本的逻辑都一样的, 前两段TLE超时, 最后的那个直接return的才能AC. 可能这个题目时间掐的比较严格吧. 大家注意便是.

// TLE, g++ complier
#include <cstdio>

#define REP(i,n) for(int i=0;i<(n);++i)
#define MAXBETS 10005
#define MAXN 100005

using namespace std;

int counts[MAXBETS];
int bets[MAXN];
int N;

int main(void) {
    scanf("%d", &N);
    REP(i,N) {
        scanf("%d", &bets[i]);
        counts[bets[i]]++;
    }
    bool found = false;
    REP(i, N) {
        if(1 == counts[bets[i]])
        {
            printf("%d\n", bets[i]);
            found = true;
            break;
        }
    }
    if(!found) printf("None\n");
    return 0;
}

// TLE with gcc compiler
#include <stdio.h>
#define MAXBETS 10005
#define MAXN 100005

int counts[MAXBETS];
int bets[MAXN];
int N;

int main(void) {
    scanf("%d", &N);
    int i = 0;
    for(i = 0; i < N; ++i) {
        scanf("%d", &bets[i]);
        counts[bets[i]]++;
    }
    int found = 0;
    for(i = 0; i < N; ++i) {
        if(1 == counts[bets[i]])
        {
            printf("%d\n", bets[i]);
            found = 1;
            break;
        }
    }
    if(!found) printf("None\n");
    return 0;
}

// AC: with gcc compiler
// last two cases takes 10 ms, the limit is 20ms
0	答案正确	0	790	11/11
1	答案正确	0	750	1/1
2	答案正确	0	790	2/2
3	答案正确	0	790	2/2
4	答案正确	10	850	2/2
5	答案正确	10	860	2/2
#include <stdio.h>

int counts[10005];
int bets[100005];
int N;

int main(void) {
    scanf("%d", &N);
    int i = 0;
    for(i = 0; i < N; ++i) {
        scanf("%d", &bets[i]);
        counts[bets[i]]++;
    }
    for(i = 0; i < N; ++i) {
        if(1 == counts[bets[i]]) {
            printf("%d\n", bets[i]);
            return 0;
        }
    }
    printf("None\n");
    return 0;
}

1041. Be Unique  注意点:

这题不要用cin, cout, 而要用scanf 和printf进行输入输出的处理, 否则超时. 另外代码写对了也不一定能过. (这里感觉PAT还是略坑), 注意找到了第一个唯一的数值就直接返回, 否则也很容易超时, 见上面三段代码的比较, 只有最后一段代码能AC.  或许最后一段能AC也只是因为服务器抖了一下, 这个也是有可能的…… >_<

Written on January 10, 2014