题目地址：http://ac.jobdu.com/problem.php?pid=1402
- 题目描述：
-
现在有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
#include <stdio.h>
#include <string.h> #define MAX 1000001 char input[MAX]; int main(void) {
int n;
int i;
int data, cnt;
while (scanf("%d", &n) != EOF){
memset(input, 0, sizeof(input));
for (i = 0; i < n; ++i){
scanf("%d", &data);
if (input[data] == 0){
input[data] = 1;
}
else if (input[data] == 1){
input[data] = -1;
}
}
cnt = 0;
for (i = 1; i < MAX; ++i)
if (input[i] == 1)
++cnt;
printf("%d\n", cnt);
i = 0;
while (i < MAX && cnt != 0){
if (input[i] == 1){
if (cnt != 1)
printf("%d ", i);
else
printf("%d\n", i);
--cnt;
}
++i;
}
}
return 0;
}
位操作
#include <stdio.h>
#include <string.h> #define MAX 125010 unsigned char input[MAX];//标记数字是否出现过
unsigned char num[MAX];//标记数字是否只出现过一次 int main(void) {
int n;
int i;
int data, index, bit, cnt;
while (scanf("%d", &n) != EOF){
memset(input, 0, sizeof(input));
memset(num, 0, sizeof(num));
for (i = 0; i < n; ++i){
scanf("%d", &data);
index = data / 8;//第data位所在单元下标
bit = data % 8;//第data位在下标index单元的bit位
if ((input[index] & (1 << bit)) == 0){
input[index] |= (1 << bit);
}
else if ((num[index] & (1 << bit)) == 0){
num[index] |= (1 << bit);
}
}
cnt = 0;
for (i = 1; i <= 1000000; ++i){
index = i / 8;
bit = i % 8;
if ((input[index] & (1 << bit)) && !(num[index] & (1 << bit)))
++cnt;
}
printf("%d\n", cnt);
i = 1;
while (i <= 1000000 && cnt != 0){
index = i / 8;
bit = i % 8;
if ((input[index] & (1 << bit)) && !(num[index] & (1 << bit))){
if (cnt != 1)
printf("%d ", i);
else
printf("%d\n", i);
--cnt;
}
++i;
}
}
return 0;
}