特殊的数——九度oj（1402）
前言昨晚搞了个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 ++)
{
补充：软件开发 , C++ ,上一个：newlisp 使用crypto模块
下一个：网络流 1009
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊