一道算法面试题

可以用位示图吧

先 求1-亿合(等差数列),在 求随即数合 ,最后在减应该能快一点吧

一亿位的bit数组占用空间怎么计算到97.6M，我算才13M左右。难道是btye

昨天刚看到的，用bitmap解

一个32位的整数32位表示32个数，1亿/32 = 3125000，使用3.125 * 4m即可保存1亿个数.
对于数n，(n-1) / 32 为其在数组中的下标，table[(n - 1) % 32]与数组中此下标的值使用或操作。

表中值为0000001, 0000010, 0000100等这样的表示方式，具体的数值使用查表法加快速度

最后算某值是否存在，使用与操作即可计算出

个人认为一千万个空间就保存随机数就好了
生成完随机数排序之后顺序比较一下就好了
即使每个采用int也是比保存1亿bit节省空间的

要是我，先把一千万的随机生成出来，存期来，判断里面有没有1和1亿，没有的加入；
然后输出相邻两个之间的数即可；

感觉这个应该是对的、、但就是看不懂

用位图排序能解决，时间复杂度为线性，而且空间占用少。
http://softbeta.iteye.com/admin/blogs/1185757

用这种方法代码实现了下。、。。

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;
	}
}