`

【腾讯】连续数打乱判断出少了哪些数?

阅读更多

1. 问题:100个连续 的数打乱 之后,随机取出1个数 ,问如何最快速 的判断出少了哪一个?

 

分析:对于所有100个连续的数,只要除余100。一定在0~99之间。一般来说,比较常规的做法就是先排序(利用Hash表定位),在循环查找。当然时间复杂度是O(2n)。现在介绍一种很牛的O(n)做法:求二进制异或运算。

 

异或运算: 0^0=1^1=0;   0^1=1^0=1。0~99个数全部异或的结果只能是0。如果缺少一个数,那么全部异或的结果正好就是那个数。为什么呢?我们做个小实验:假如有四个数:  0001  0010,0101, 0110 排列成一个matrix.

                                        bits:      1     2    3      4

                                                     0     0    0      1

                                                     0     0    1      0

                                                     0     1    0      1

                                                     0     1    1      0

                                    全部异或:  0     0    0      0

我们可以下结论了,要全部异或的结果为0,那么所有bit位上的1的个数必须为偶数。 反过来说:如果其中有一个数不存在了(比如0001),那么少0的的bit位上的值不变(因为1的个数还是偶数),而少1的bit位上的值就变成了1(1的个数为奇数了)。

 

这样0~99的道理也就一样了,所以异或的结果就是少的那个值。代码如下:

int data=0;
for(int i=1;i<=99;i++){
	if(i==78)  //少78
	      continue;
	data=data^i;
}
System.out.println(data);

 

2. 问题:100个连续 的数打乱 之后,随机取出2个数 ,问如何最快速 的判断出少了哪两个? (注意少2个数了)

 

分析:常用的做法可以先创建一个100个结构的Hash表,然后循环一次将所有数哈希100之后的位置上置1。然后顺序循环100次查找这个Hash表。前后需要O(2n)的时间。然而有没有更快速的做法呢?当然,直接操作bit.

 

假设我们有32个连续打乱的数字(0~31)缺少两个数2和11,希望把标记1标记在一个32位上。也就是一个整形变量,标记完之后就成为了:

                 bits position    31   30  29  28  .......  11   10   ....  2    1    0

                         int   a=     1     1    1    1   .......   0     1    ....  0    1    1    (缺少数的bit位上为0)

至于如何标记成为a,我们可以看看下面的小段代码:

long bits=0;
for(int i=0;i<32;i++){
	long bitMove=1;
	if(i==2||i==11)
		continue;
	bitMove=bitMove<<i;
	bits=bits | bitMove;
	System.out.println(bits+"  :  "+Long.toBinaryString(bits));
}
 

此时我们将数字a每8位作为一个数字b,如果b==255, 则说明全部8位都是1(没有缺少数字)。如果b!=255,则说明有某些位是0(有数字缺少),然后再在不等于255的8 bits上顺序查找等译0的位数即可。这样就相当于原来需要顺序查找32 bits(查找32次)。而现在只需要先查找4个8位的块,然后再需找某个8位块中的bit(也就是需要4+8=12次)即可。这就是分块查找的基本原理了。

 

通过一个32个连续的数,我们发现了敲门。这样对于100个连续的数呢?很简单,我们需要4个32位就够了。注意:由于最高位如果是1的话,整形数据将会变成负数,不方便我们的计算。因此我们用long数据来存储32个位数。

 

代码如下:

public class Test{
	
	public static void main(String[] args){
		//需要4个32位数据,用long存储为了避开int存储可能带来的负数。
		//intBits[0]的最低32位标识数据0~31
		//intBits[1]的最低32位标识数据32~63,
		//intBits[2]的最低32位标识数据64~95,
		//intBits[3]的最低4位标识数据96~99
		long[] intBits={0L,0L,0L,0L}; 
		
		//用100bit位标识是否存在0~99的数据
        //此时需要循环的次数为100次,时间复杂度O(n),n为连续的data数量。
		int loop=0;
		for(int data=0;data<=99;data++){
			long bitMove=1;
			if(data==2||data==11) //缺少数据2和11
				continue;
			bitMove=bitMove<<(data-32*(data/32)); 
			intBits[data/32]=intBits[data/32] | bitMove;
			loop++;
		}
		//中间打印标识结果
		System.out.print("标识结果(循环"+loop+"次):");
		for(int i=3;i>=0;i--)
			System.out.print(Long.toBinaryString(intBits[i]));
		System.out.println();
		
		//分块查找,每8bit一块,一共需要100/8=13块
		//其中如果8bit全部是1,则该数据等于2^8-1=255
		//前3个intBits都全部位数都用来标识数据
		loop=0;
		int zeroSize=0;
		for(int i=0;i<4;i++){
			long bits=intBits[i];
			long eightBits=0;
			int eightSize=0;
			while((eightBits=bits%256)!=0){
				System.out.println("第"+((eightSize+1)+i*4)+"个8bits块:"+Long.toBinaryString(eightBits));
				if(i<3&&eightBits!=255){
					for(int j=0;j<8;j++){
						loop++;
						if(eightBits%2==0){
							zeroSize=j+eightSize*8+i*32;
							System.out.println("   zero size="+zeroSize);
						}
						eightBits=eightBits>>1;
					}
				}
				bits=bits/256;
				eightSize++;
				loop++;
			}
		}
			
		System.out.println("标识后查找需要循环"+loop+"次");

	}	
}

 这段代码只需要循环98+29=117次,少于一般情况下的200次。

 

 

3. 问题:有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数?(不准用位图)

  我想用分块查找的思想,首先开辟一个a[100][1001]存储结构,遍历10W个数存放这个结构

int[][] a=new[100][1001];
  for(int i=0;i<99998){
        a[i/1000-1][i%1000+1]=1;
        a[i/1000-1][0]++;  //记1000个数是否已经满了。
  }

  for(int j=0;j<100;j++){
      if(a[j][0]<1000){ //这1000个数里面有数少了
           for(int k=1;k<1000;i++){
               if(a[j][k]!=1){
                    System.out.println("少了的呢个数就是:"+(j*1000+k));
               }
           }
      }
  }

 

性能分析: 首先循环99998次为数组设置标志位。然后双重循环(其实真正需要双循环的是有2次,因为就少了2个数),因此双重循环的次数因该是: 100(块查找次数)+2*1000=2100次。
        一共循环99998+2100  因此效率是O(n+m) 其中n为待查找数字的个数(10W),m为分割的块数与快内查找的次数。如果n远远大于m,则查询效率接近于O(n)。因此这种查找数据越多效率越好。

 

分享到:
评论
3 楼 weiqiang.yang 2010-06-23  
pcdevelop 写道
如果这里的100换成其他的数,结果就很不尽然了。
1^2^3^4=4
1^2^3^4^5=1
1^2^3^4^6=7
......
如上,4,5,6的异或之和均不为0,3,7,11,15,19的异或之和均为0。但不清楚规律是什么?


异或^运算满足交换律,结合律
a^b = b^a
a^b^a = b

假设有原始数组A,去掉一个数字x之后的数组为B
定义运算xor(A) = A[0]^A[1]^A[2]....A[n-1]

因此有
xor(A) = xor(B) ^ x
xor(A)^xor(B) = xor(B) ^ x ^xor(B)

于是x = xor(A) ^ xor(B)
2 楼 seraphim871211 2010-06-19  
pcdevelop 写道
如果这里的100换成其他的数,结果就很不尽然了。
1^2^3^4=4
1^2^3^4^5=1
1^2^3^4^6=7
......
如上,4,5,6的异或之和均不为0,3,7,11,15,19的异或之和均为0。但不清楚规律是什么?


实际上这种方法并不通用,更好的做法是:
X = 1^2^3^4 = 4
Y = 1^2^4 = 7
X^Y = 3

规律就是两个集合中的元素一起做异或操作,结果就是少了的那个数字。
1 楼 pcdevelop 2010-06-02  
如果这里的100换成其他的数,结果就很不尽然了。
1^2^3^4=4
1^2^3^4^5=1
1^2^3^4^6=7
......
如上,4,5,6的异或之和均不为0,3,7,11,15,19的异或之和均为0。但不清楚规律是什么?

相关推荐

Global site tag (gtag.js) - Google Analytics