33,007
社区成员
发帖
与我相关
我的任务
分享百度曾经考试过的一个算法题：从2.5亿个数字里面找出不重复的数字的个数
问题描述如下：
有2.5亿个整数(这2.5亿个整数存储在一个数组里面，至于数组是放在外存还是内存，没有进一步具体说明)；
要求找出这2.5亿个数字里面，不重复的数字的个数；
另外，可用的内存限定为600M；
要求算法尽量高效，最优；
有2.5亿个整数(这2.5亿个整数存储在一个数组里面，至于数组是放在外存还是内存，没有进一步具体说明)；
要求找出这2.5亿个数字里面，不重复的数字的个数；
另外，可用的内存限定为600M；
要求算法尽量高效，最优；
...全文
请发表友善的回复…
发表回复
索隆 2012-05-07
- 打赏
- 举报
看了半天，没看懂原题，我理解的是：有一个数组里面有随机的2.5亿个数字，找出这里面只出现过一次的数字有多少个？是不是这个问题？
小弟季义钦 2012-05-06
- 打赏
- 举报
[Quote=引用 215 楼 的回复:]
用java实现 吧数据数据放到set集合里然后 但会set的size
[/Quote]
2.5亿数据。。。你能放进内存？
用java实现 吧数据数据放到set集合里然后 但会set的size
[/Quote]
2.5亿数据。。。你能放进内存？
小弟季义钦 2012-05-06
- 打赏
- 举报
bitMap方法真的太傻了。。。。。。。
如果我的2.5亿个数字都是long long型(64bit)，你就需要 2^64/8个字节的空间，你自己算算，这早就大于你的内存了。。。
别局限于int型数组了。
如果我的2.5亿个数字都是long long型(64bit)，你就需要 2^64/8个字节的空间，你自己算算，这早就大于你的内存了。。。
别局限于int型数组了。
luofl_ 2011-11-04
- 打赏
- 举报
Mark.
让爱延续 2010-10-16
- 打赏
- 举报
学习。
JohnsonElizeee 2010-10-11
- 打赏
- 举报
/* using two 256M array to record the existing state is the best way. */
int duplicated(int all[], int size)
{
bit st1[256M] = {0}, st2[256M] = {0};
int cnt = 0;
for(dat : all)// for each data in all-data set
{
if (dat < 2^31) {
if(st1[dat] == 0) st1[dat] = 1;
else if(st2[dat] == 0) { st2[dat] = 1; cnt++; }
}
}
reset st1 and st2;
for(dat : all)// for each data in all-data set
{
if (dat >= 2^31) {
dat -= 2^31;
if(st1[dat] == 0) st1[dat] = 1;
else if(st2[dat] == 0) { st2[dat] = 1; cnt++; }
}
}
return cnt;
}
/* the time complexity is not a constant, O(1), it's O(2 * size/2), it means O(n). */
/* space complexity is O(1), a constant size depending on your processing division.*/
/* if we need to process one billion data with type int, this algorithm can also */
/* work well. because the precondition: 0 <= all[i] < 2^32. */
/* Whitout real implementation and full test, if any bug, any reply will be */
/* appreciated. */
int duplicated(int all[], int size)
{
bit st1[256M] = {0}, st2[256M] = {0};
int cnt = 0;
for(dat : all)// for each data in all-data set
{
if (dat < 2^31) {
if(st1[dat] == 0) st1[dat] = 1;
else if(st2[dat] == 0) { st2[dat] = 1; cnt++; }
}
}
reset st1 and st2;
for(dat : all)// for each data in all-data set
{
if (dat >= 2^31) {
dat -= 2^31;
if(st1[dat] == 0) st1[dat] = 1;
else if(st2[dat] == 0) { st2[dat] = 1; cnt++; }
}
}
return cnt;
}
/* the time complexity is not a constant, O(1), it's O(2 * size/2), it means O(n). */
/* space complexity is O(1), a constant size depending on your processing division.*/
/* if we need to process one billion data with type int, this algorithm can also */
/* work well. because the precondition: 0 <= all[i] < 2^32. */
/* Whitout real implementation and full test, if any bug, any reply will be */
/* appreciated. */
JohnsonElizeee 2010-10-11
- 打赏
- 举报
mark
xfly008 2010-10-11
- 打赏
- 举报
都好强啊，学习ing
tyzqqq 2010-09-18
- 打赏
- 举报
xiaotanyu13 2010-09-06
- 打赏
- 举报
[Quote=引用 9 楼 oo 的回复:]
不重复的数字的个数应该是重复的数字只算一次，比如1，2，2算2个
[/Quote]
只有一个问题 2 是不是重复了？？？
不重复的数字的个数应该是重复的数字只算一次，比如1，2，2算2个
[/Quote]
只有一个问题 2 是不是重复了？？？
musiccoder 2010-08-27
- 打赏
- 举报
学习啊
ice_coffee_0 2010-08-03
- 打赏
- 举报
把所有的数存入数据库，用Sql语名查询。
chensb666 2010-03-29
- 打赏
- 举报
mark
三断笛 2010-02-28
- 打赏
- 举报
钱能的C++程序设计教程上有...
shunzi__1984 2009-02-12
- 打赏
- 举报
学习
weizhe86 2009-02-01
- 打赏
- 举报
我是这样理解了一下高手的意思的
分出512M空间作4G的bitmap，分出32M作250M的bitmap
将250M的单个数据为a，a的数值在4G之内，a的序号在250M之内
a数值对应的bit为0表示之前没有读过a重复的数，1表示已经读过。a序号对应的bit为0表示无重复，1为重复
while循环读入a：
f＝a序号 ＃自加一得到
对a值bit，if 为零：置一；else：a序号bit，置一
while循环读入a：
f＝a序号 ＃自加一得到
对a序号bit，if 为一：对a值bit，清零
统计数值bitmap中置一的数量
分出512M空间作4G的bitmap，分出32M作250M的bitmap
将250M的单个数据为a，a的数值在4G之内，a的序号在250M之内
a数值对应的bit为0表示之前没有读过a重复的数，1表示已经读过。a序号对应的bit为0表示无重复，1为重复
while循环读入a：
f＝a序号 ＃自加一得到
对a值bit，if 为零：置一；else：a序号bit，置一
while循环读入a：
f＝a序号 ＃自加一得到
对a序号bit，if 为一：对a值bit，清零
统计数值bitmap中置一的数量
xdspower 2008-09-21
- 打赏
- 举报
[Quote=引用 59 楼 xdspower 的回复:]
注意原题：
问题描述如下：
有2.5亿个整数(这2.5亿个整数存储在一个数组里面，至于数组是放在外存还是内存，没有进一步具体说明)；
要求找出这2.5亿个数字里面，不重复的数字的个数；
另外，可用的内存限定为600M；
要求算法尽量高效，最优；
－－－－－－－－－－－－－－
是只计算个数，而不要求知道是那些数字
所以最简单的办法其实是这样的
数字进行无格式处理（这样可以一一对应地址）
定义两个256M的位数组a[]…
[/Quote]
中有一个小bug，就是
flag b[a^31]={0};
应该为
flag b[2^31]={0};
注意原题：
问题描述如下：
有2.5亿个整数(这2.5亿个整数存储在一个数组里面，至于数组是放在外存还是内存，没有进一步具体说明)；
要求找出这2.5亿个数字里面，不重复的数字的个数；
另外，可用的内存限定为600M；
要求算法尽量高效，最优；
－－－－－－－－－－－－－－
是只计算个数，而不要求知道是那些数字
所以最简单的办法其实是这样的
数字进行无格式处理（这样可以一一对应地址）
定义两个256M的位数组a[]…
[/Quote]
中有一个小bug，就是
flag b[a^31]={0};
应该为
flag b[2^31]={0};
eteck 2008-09-21
- 打赏
- 举报
看懂xdspower的思路了，原来是考虑重复出现的为0次，而不是1次。学习中
qinguan0619 2008-09-20
- 打赏
- 举报
学习~~~
qinguan0619 2008-09-20
- 打赏
- 举报
学习~~~
加载更多回复（223）
