判断数组中包含重复数(大数中取重复)

判断数字是否出现在40亿个数中；找出一组数中不重复的数字，即只出现一次的数字；判断一个成员个数为n，成员取值在1 ~ n的数组中是否有重复的成员

问题一

给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?

算法思路：
unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即可。
其实这个类似的应用是用户在线离线系统，一个用户在线还是离线。

1024B=1KB 1024KB=1MB 1024MB=1GB
2^32B=2^32/1024/1024/1024=4GB

问题二

在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。
算法思路：
方案一、采用hase的方法，将2.5亿个数拆分成多个小文件，然后取出每个小文件中不重复的数

方案二、采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

问题三

判断一个成员个数为n，成员取值在1 ~ n的数组中是否有重复的成员

算法思路：
方法1.
对数组进行排序（快速，堆），然后比较相邻的元素是否相同。
时间复杂度为O(nlogn)，空间复杂度为O(1)。
方法2、
使用bitmap方法。
定义长度为N/8的char数组，全部初始化为0，每个bit表示对应数字是否出现过。遍历数组，数字出现，将对应bit设置为1，使用 bitmap对数字是否出现进行统计。
时间复杂度为O(n)，空间复杂度为O(n)。
方法3、
遍历数组，假设第 i 个位置的数字为 j ，则通过交换将 j 换到下标为 j 的位置上，直到所有数字都出现在自己对应的下标处，或发生了冲突。
时间复杂度为O(n)，空间复杂度为O(1)。
方法3示例代码如下：

#include <cstdlib> 
#include <iostream> 
#include <ctime> 
#include <algorithm> 
using namespace std;  
const int MAX = 100;  
bool isDuplicate(int val[])  
{  
    for(int i=0; i<MAX; i++)  
    {  
        if(val[i] != i)  
        {  
            if(val[i] != val[val[i]])  
                swap(val[i],val[val[i]]);  
            else  
                return true;  
        }  
    }  

    return false;  
}  
int main(int argc,char *argv[])  
{  
    int val[MAX];  

    srand((unsigned)time(NULL));  

    cout << "init data: " << endl;  
    for(int i=0; i<MAX; i++)  
    {  
        int temp = rand() % MAX;  
        val[i] = temp;  
        cout << temp << " ";  
    }  
    cout << endl;  

    bool flag = isDuplicate(val);  
    if(flag)  
        cout << "has duplicate elem" << endl;  
    else  
        cout << "no duplicate elem" << endl;  

    system("PAUSE");  
    return EXIT_SUCCESS;  
}

参考：
http://blog.163.com/xychenbaihu@yeah/blog/static/132229655201282054856381/