频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
特殊的数——九度oj(1402)
2013-01-24 16:38:29      个评论      
收藏   我要投稿
前言

昨晚搞了个acm题,当时没考虑到内存限制,用了int数组,然后链表动态分配的方法,结果内存不够无法ac,今天考虑了一下,用数组唯一性的原理就可以实现了。难点在于用char数组存储数据,可以节约内存空间。

 

特殊的数

题目描述:

现在有n个数,其中有一些出现了一次,一些出现了两次,一些出现了很多次。现在要求你找出那些只出现一次的数,并按升序输出。

输入:

本题有多组case。

每个case有两行,第一行输入一个n,表示有n个数,1<= n <= 1000000。

第二行有n个数字。每个数字的大小范围[1, 1000000]。

输出:

每次输出有两行。

第一行输出一个整数,表示出现一次的数的个数。

第二行按升序输出出现次数为一次的数字,两个数字之间用空格隔开。

样例输入:

5

1 2 2 3 3

7

1 2 2 3 4 4 2

2

2 2

样例输出:

1

1

2

1 3

0

AC代码

key唯一性

[cpp]  

#include <stdio.h>  

#include <stdlib.h>  

#include <string.h>  

  

#define max 1000001  

  

  

int main()  

{  

    int i, n, count, temp, j;  

    char a[max];  

  

    while(scanf("%d", &n) != EOF)  

    {  

        memset(a, 0, sizeof(a));  

  

        for(i = count = 0; i < n; i ++)  

        {  

            scanf("%d", &temp);  

  

            if(a[temp] == 0)  

            {  

                a[temp] += 1;  

                count ++;  

            }else if(a[temp] == 1)  

            {  

                a[temp] += 1;  

                count --;  

            }else  

            {  

                a[temp] += 1;  

            }  

        }  

  

  

        printf("%d\n", count);  

        if(count)  

        {  

  

            for(i = j = 0; i < max; i ++)  

            {  

                if(a[i] == 1)  

                {  

                    if(j == count - 1)  

                        printf("%d\n", i);  

                    else  

                        printf("%d ",i);  

                    j ++;  

                }  

            }  

        }  

    }  

    return 0;  

}  

 

不考虑内存,可以用链表&&排序实现,感觉自己写的不错,也贴出来吧(这个没ac,因为内存超了限制,但是重要在学习方法)

[cpp]  

#include <stdio.h>  

#include <stdlib.h>  

#include <string.h>  

  

struct lnode  

{  

    int data;  

    struct lnode *next;  

};  

  

  

int compare(const void *a, const void *b);  

void createlist(struct lnode *, int);  

void cleanlist(struct lnode *);  

  

int main()  

{  

    int num[1000001];  

    int i, n, j, k;  

    struct lnode *p;  

    while(scanf("%d", &n) != EOF)  

    {  

        //初始化数据  

        memset(num, 0, sizeof(num));  

        struct lnode *head = malloc(sizeof(struct lnode));  

        head->data = 0;  

        head->next = NULL;  

  

        //接收输入数据  

        for(i = 0; i < n; i ++)  

        {  

            scanf("%d", &num[i]);  

        }  

  

        //快速排序,调用系统qsort  

        qsort(num, n, sizeof(num[0]), compare);  

  

        for(i = j = 0; i < n; i ++)  

        {  

            if(num[i] != num[i + 1])  

            {  

                createlist(head, num[i]);  

                j ++;     

            }else  

            {  

                for(k = i; k < n; k ++)  

                {  

                    if(num[i] != num[k])  

                    {  

                        break;  

                    }  

                }  

                i = k - 1;  

            }  

        }  

  

        //打印输出  

        printf("%d\n", j);  

        for(i = 0, p = head->next; p && i < j; p = p->next, i ++)  

        {  

            if(i == j - 1)  

                printf("%d\n", p->data);  

            else  

                printf("%d ", p->data);  

        }  

  

        //清理链表  

        cleanlist(head);  

    }  

  

    return 0;  

}  

  

int compare(const void *a, const void *b)  

{  

    int sign;  

    sign = (*(int *)a - *(int *)b) * -1;  

    return sign;  

}  

  

void createlist(struct lnode *head, int data)  

{  

    struct lnode *s = malloc(sizeof(struct lnode));  

    s->data = data;  

    s->next = head->next;  

    head->next = s;  

}  

  

void cleanlist(struct lnode *head)  

{  

    struct lnode *p;  

  

    for(p = head; p; p = head)  

    {  

        head = head->next;  

        free(p);  

    }  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:网络流 1009
下一篇:newlisp 使用crypto模块
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站