锁定老帖子 主题:一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-10-01
可以用位示图吧
|
|
返回顶楼 | |
发表时间:2011-10-01
先 求1-亿合(等差数列),在 求随即数合 ,最后在减应该能快一点吧
|
|
返回顶楼 | |
发表时间:2011-10-01
yangelhun 写道 evil9999 写道 申请一亿位的数组空间,全部置0,然后以随机数为数组索引,将该位置1,遍历数组,输出位不为1的索引
一亿位的数组空间占用空间97.6M 一亿位的bit数组占用空间怎么计算到97.6M,我算才13M左右。难道是btye |
|
返回顶楼 | |
发表时间:2011-10-02
昨天刚看到的,用bitmap解
|
|
返回顶楼 | |
发表时间:2011-10-02
最后修改:2011-10-02
一个32位的整数32位表示32个数,1亿/32 = 3125000,使用3.125 * 4m即可保存1亿个数.
对于数n,(n-1) / 32 为其在数组中的下标,table[(n - 1) % 32]与数组中此下标的值使用或操作。 表中值为0000001, 0000010, 0000100等这样的表示方式,具体的数值使用查表法加快速度 最后算某值是否存在,使用与操作即可计算出 |
|
返回顶楼 | |
发表时间:2011-10-03
个人认为一千万个空间就保存随机数就好了
生成完随机数排序之后顺序比较一下就好了 即使每个采用int也是比保存1亿bit节省空间的 |
|
返回顶楼 | |
发表时间:2011-10-04
要是我,先把一千万的随机生成出来,存期来,判断里面有没有1和1亿,没有的加入;
然后输出相邻两个之间的数即可; |
|
返回顶楼 | |
发表时间:2011-10-06
jorneyR 写道 一个32位的整数32位表示32个数,1亿/32 = 3125000,使用3.125 * 4m即可保存1亿个数.
对于数n,(n-1) / 32 为其在数组中的下标,table[(n - 1) % 32]与数组中此下标的值使用或操作。 表中值为0000001, 0000010, 0000100等这样的表示方式,具体的数值使用查表法加快速度 最后算某值是否存在,使用与操作即可计算出 感觉这个应该是对的、、但就是看不懂 |
|
返回顶楼 | |
发表时间:2011-10-06
用位图排序能解决,时间复杂度为线性,而且空间占用少。
http://softbeta.iteye.com/admin/blogs/1185757 |
|
返回顶楼 | |
发表时间:2011-10-06
jorneyR 写道 一个32位的整数32位表示32个数,1亿/32 = 3125000,使用3.125 * 4m即可保存1亿个数.
对于数n,(n-1) / 32 为其在数组中的下标,table[(n - 1) % 32]与数组中此下标的值使用或操作。 表中值为0000001, 0000010, 0000100等这样的表示方式,具体的数值使用查表法加快速度 最后算某值是否存在,使用与操作即可计算出 用这种方法代码实现了下。、。。 public class test { public static void main(String[]args){ //<64 int []a=new int[100]; int[] b={3,23,678,999,1234}; for(int i=0;i<b.length;i++){ int index=b[i]/32; int bitindex=b[i]%32; //设置对应的位数为1 a=new test().set1At(a,index, bitindex);//bitindex count from right,the first bitindex is 1; //System.out.println(a[index]); } //下面是找出存在的数字 for(int i=0;i<a.length;i++){ if(a[i]!=0){ int bindex=i*32; int m=a[i]; int j=1; while(m!=0){ if(m%2!=0){ System.out.println(bindex+j); } m=m>>>1; j++; } } } } public int[] set1At(int[] a,int index,int bitIndex){ a[index]=a[index]|((1<<(bitIndex-1))); //System.out.println(1<<(bitIndex-1)); return a; } } |
|
返回顶楼 | |