PAT题目

2012-09-20

PAT题目求助For each test case, print the winning number in a line. If there is no winner, print No

PAT题目求助
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

也就是找出一个数组中最靠前的不重复的第一个元素（数组元素最多有10的五次方）

C/C++ code

#include <stdio.h>#include <stdlib.h>#define MAX 100000struct data{    int num;    int flag;};struct data s[MAX];int main(){    long int N;    long int i, j;    int r, flag = 0;        scanf("%ld", &N);        for (i = 0; i < N; i++)    {        scanf("%d", &(s[i].num));        s[i].flag = 0;    }        for (i = 0; i < N; i++)    {        flag = 0;        if (s[i].flag == 0)            r = s[i].num;        else             continue;                    for (j = i + 1; j < N; j++)             if (r == s[j].num && i != j)             {                 flag = 1;                 s[j].flag = 1;                 break;             }                if (flag == 0)            break;        }        if (i == N && N != 1)        printf("None");    else         printf("%d", r);        return 0;        }

这样提交后会有case超时求解答

[解决办法]
我按照快排的思想写了一个，你测试一下是否超时？
另外希望你把原题贴出来，我想看看输入数据的范围是否确定，如果确定的话我有O（n）的算法。

C/C++ code

#include <stdio.h>#include <stdlib.h>int bss (int a[], int s, int e, int v) //二分查找{    int m;    while (s <= e)     {        m = (s + e) / 2;        if (a[m] == v)         {            return m;        }         else if (a[m] > v)         {            e = m - 1;        }        else        {            s = m + 1;        }                }    return -1;}void qsort(int a[], int begin, int end)//快速排序{    if (begin<end)    {                int b=begin;        int e=end;        int temp=a[b];        while(b<e)        {            while (b<e && a[e]>=temp)            {                e--;            }            a[b]=a[e];            while (b<e && a[b]<=temp)            {                b++;            }            a[e]=a[b];        }        a[b]=temp;        qsort(a, begin, e-1);        qsort(a, e+1, end);    }    return;    }void main(){    int len;    scanf("%d", &len);    int *a1 = (int*)malloc(sizeof(int)*len);    int *a2 = (int*)malloc(sizeof(int)*len);    int i;    for(i=0; i<len; ++i)    {        scanf("%d", &a1[i]);        a2[i] = a1[i];    }    qsort(a2, 0, len-1);    int pos;    for(i=0; i<len; ++i)    {        pos = bss (a2, 0, len-1, a1[i]);        if(pos>0 && pos<len-1)        {            if(a2[pos-1]!=a2[pos] && a2[pos+1]!=a2[pos])            {                printf("%d", a1[i]);                return;            }        }        else        {            if(pos==0)            {                if(a2[0]!=a2[1])                {                    printf("%d", a1[i]);                    return;                }            }            else            {                if(a2[len-1]!=a2[len-2])                {                    printf("%d", a1[i]);                    return;                }            }        }    }    printf("None");}
[解决办法]
晕。。数字范围有定，那就用位图吧，100K BITS /8 = 12.5k bytes 内存，位图完全能够胜任。而且 O(N) 的复杂度就能出结果了。

热点排行

C语言

PAT题目