非一般的数——九度oj（1402）

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

题目描述：

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

输入：

本题有多组case。

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

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

输出：

每次输出有两行。

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

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

样例输入：

51 2 2 3 371 2 2 3 4 4 222 2

样例输出：

1121 30

#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]);}//快速排序，调用系统qsortqsort(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);elseprintf("%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);}}