非高手不能解决的问题（关于删除重复数的）
问题：
一个文件data.txt中有10^9个数（均小于10^10），存在重复。要将文件中所有重复的数字删除，得到一个新文件，并要求新文件中原来在前的数据仍在前。
求最优算法。
最优算法不仅要快，还要是内存使用不大的。
若用哈希表，采用一位对应一个数，虽然复杂度是O(n），但是空间需要几百兆，内存消耗过大。哪为兄弟可给出更好的算法？
[解决办法]
hash最快，空间要求不算厉害啊，现在的内存中可以满足的，而且你仅仅需要位操作，所以空间还可以缩减。
[解决办法]
没办法，用其他排序的话，只能判断哪些重复，删了以后根本就写不回去，
况且速度不是一个级别的，怎么让人相信“速度也比较快”
一个整数也就1 bit的空间
如果内存吃紧，就建临时文件好了
[解决办法]
不太相信，楼主把你的算法贴出来看看啊
[解决办法]
首先，感谢lz满足个人好奇心，不过这个还是hash
lz能否解释一下：
j=0;
col = mid%256;
flag = true;
while( j <v3len )
{
mid/=256;
line = mid%256;
if( !Index[ j ][ col ][ line ] )
{
Index[ j ][ col ][ line ] = true;
flag = false;
}
++j;
col = line;////看不懂col和line什么关系？
}
另外，我说过“一个整数也就1 bit的空间”，这个是保存所有整数的最小限度
[解决办法]
10^10就是1后面10个0,其实不大
1,作一个串有10^10位,1G多!!!
2,循环每读数
这个位图上没有: 置位,输出
楼上说的128B可能是没明白,位图不是数
第1个数是1,你置1,第2个数是2,你置2,第3个数是3你怎么办?
再有10^10,这个数整形放不下,得用long
再有2^19确实很少,可10^10有36位长,你只判断后19位是不是重=没判断吧
这是我写的程序
1,gmp是PHP里大数运算库,100位长的数就得用它了
2,gmp_scan0是从第i位找0返回第1个是0的位,与i比较看这位是否被置位
3,gmp_setbit是置位函数,参数是第几位
4,由于PHP默认的整形是4字节的所以不能直接比较用bc库的比较函数bccomp
<?
$map = gmp_init();
$fp = fopen( "old.txt ", "r ");
$ft = fopen( "new.txt ", "w ");
while($i = trim(fgets($fp,10)))
{
if(bccomp(gmp_scan0($map,$i),$i)==0)
{
gmp_setbit($map,$i);
fputs($ft,$i. "\n ");
}
}
fclose($fp);
fclose($ft);
?>
[解决办法]
楼主是想转换进制来表示，这样数据容量就小了（数据位数就少了），但犯了点逻辑错误，这仅仅是表示方式变化，数据量是不变的，也就不能减少最少空间，其实严格说来这个步骤是多余的，而且楼主给出的结论“只需要256*256*8=2^19=512KB的空间就可以了。我用512KB的空间，是为了加速，实际上，甚至可以只用32*2*2=128B的空间就可以了。”也是错误的。
按楼主题设，数据范围是
10^10，则log(10^10)=log(10)*10=10，而log(256)=2.4,则范围在10^10的数据，用256进制表示，大概需要10/2.4> 4，既最高要5位，而楼主想当然的认为3位就表示完了，当然就有了上面的错误了。如果不信，请楼主用一个10^10的序列数据进行测试，就可以发现错误了，很可能数据要越界了。
[解决办法]
问题：
一个文件data.txt中有10^9个数（均小于10^10），存在重复。要将文件中所有重复的数字删除，得到一个新文件，并要求新文件中原来在前的数据仍在前。
求最优算法。
最优算法不仅要快，还要是内存使用不大的。
若用哈希表，采用一位对应一个数，虽然复杂度是O(n），但是空间需要几百兆，内存消耗过大。哪为兄弟可给出更好的算法？
===============================================================================
不用内存，可以利用外存空间，使用哈希表复杂度O（n）
[解决办法]
1 bit数据量只能表示两种状态，要保存10^9个有和无两种状态的信息，就至少要10^9 bit
除非有些数的状态信息不用保存
简单些，0-7范围内的n个整数删除重复，要保存全部信息至少8 bit
不知道lz如果只用1 bit怎么判断重复
