使用位图法进行排序和查找

JerryXia 发表于 , 阅读 (1,688)

如何在1MB的空间里面对一千万个整数进行排序?并且每个数都小于1千万。实际上这个需要1.25MB的内存空间(这里所说的空间是考虑用位图表示法时,每一位代表一个数,则1千万/(102410248) 约为1.25MB )。

先来随机生成[0, n)之间不重复的随机数(关键思想为:先把所有可能数顺序放到数组,然后打乱顺序,则保证不重复)

排序

for (i = 0; i < n; ++i)
    a[i] = i;
    
for (i = 0; i < n; ++i){
    pos = rand()%(n – i) + i;
    t = a[i];
    a[i] = a[pos];
    a[pos] = t;
}  
//初始化sr
foreach() {
    sr[a[i]] = 1;
    i++;  
}
//依序输出sr

查找

假设你要查找有序排列的整数集合,但其中缺少几个数,要求查找出缺少的那几个数,这是用位图法合适;

方法跟以上查找用的一样;主要是阐述一下思想,代码仅供参考!^_^

添加新评论