判断数组中包含重复数(大数中取重复)
判断数字是否出现在40亿个数中;找出一组数中不重复的数字,即只出现一次的数字;判断一个成员个数为n,成员取值在1 ~ n的数组中是否有重复的成员 问题一给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中? 算法思路: 1024B=1KB 1024KB=1MB 1024MB=1GB 问题二在2.5亿个整数中找出不重复的整数,内存不足以容纳这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的数组中是否有重复的成员 算法思路: #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;
}
参考: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |