九度oj 特殊的数字

题目描述：

现在有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

样例输出：

分析：由于题目限定了所能用的空间，所以要使用位压缩。开一个char数组，大小为MAX/8，表示用一个二进制位存一个数字的状态：1：表示该数字只出现了一次，0：表示与1相反的情况：

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
const int M=1010;
const int N=100010;
int n;
char hash[N/8],vis[N/8];
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        memset(hash,0,sizeof(hash));
        memset(vis,0,sizeof(vis));
        int value,index,sum=0,minn=1000100,maxx=-1;
        for (j=0;j<n;j++)
        {
            scanf("%d",&value);
            if (maxx<value) maxx=value;
            if (minn>value) minn=value;
            index=value>>3;   // value应存放在hash[]里的位置下标
            value&=7;  //  value 在字符中二进制位置
            if (!(hash[index] & 1<<value)) { hash[index]|=1<<value; sum++;} // value 没有出现过
            else if (!(vis[index] & 1<<value)) {  // value 第二次出现
                vis[index]|=1<<value; //  用vis数组标记
                sum--;  // 合法解总数减一
            }
        }
        int k=0;
        if (sum){
            printf("%d\n",sum);
            for (i=minn;i<=maxx;i++) {
                index=i>>3;
                int e=i;
                i&=7;
                if (hash[index] & 1<<i && !(vis[index] & 1<<i)){
                    if (k<sum-1) printf("%d ",e);
                    else printf("%d\n",e);
                    k++;
                }
                i=e;
            }
        }
        else cout<<0<<endl;
    }
}