. 问题：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)。因此这种查找数据越多效率越好。
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^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。但不清楚规律是什么？
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)