java 找出重复的数字

旧城等待， 2021-09-24 12:32 373阅读 0赞

这是一个经典的题型，比如：有1亿个数字，找出其中重复的。

最直观的写法就是双重循环了，但是效率过低。再就是先排序再遍历，又总感觉不太直接。后来偶然查到BitSet有相应的api来处理这个问题，查了下源码，还挺有意思的，记录一下。

直接上代码

public class Test05 { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		int[] arr = new int[10000000];
    		for(int i = 0; i < arr.length; i++) { 
    			arr[i] = i;
    		}
    		arr[arr.length - 1] = arr.length - 10;//构造一个有重复数字的数组
    		
    		aaa(arr);
    		
    	}
    	
    	public static void aaa(int[] arr) { 
    		long time1 = System.currentTimeMillis();
    		
    		int max = 1;
    		for(int i: arr) { 
    			max = i > max ? i : max;//查找最大值
    		}
    		
    		long[] temp = new long[(max >> 6) + 1]; 
    		
    		for(int i: arr) { 
    			if((temp[i >> 6] & (1l << i)) == 0) { //判断是否重复
    				temp[i >> 6] |= 1l << i;
    			}else { 
    				System.out.println(i + " is duplicate");
    				//break;
    			}
    		}
    		
    		long time2 = System.currentTimeMillis();
    		
    		System.out.println((time2 - time1) + "ms");
    	}
    
    }

（相对于源码，仅省略了自动扩容和校验）

全是位运算很吓人，但是实际上比冒泡排序还简单。

原理  
如果说桶排序是投机取巧，那这个算法就是投机取巧上继续投机取巧。首先找到最大的数，然后除以64（也就是移6位）以确定桶的数量（源码中是动态改变桶数组的，每加入一个新数字，都会算出它所应该在的位置，如果比当前数组长度大，则复制数组进行扩容。由于与算法本身无关，写起来又很麻烦，省略掉）。对于每一个数字，它所在的桶数组的下标是除以`64后的整数`部分，它所对应的值是`1l << 除以64的余数` 。举几个例子：

对于数字3，它除以64为0，余数是3。那么它应该在桶数组下标0的位置，它的值用2进制表示为1000。
    对于数字4，它除以64为0，余数是4。那么它应该在桶数组下标0的位置，它的值用2进制表示为10000。由于插入数组时用了或运算符，最终结果应该为11000。

在查找重复时也是完全一样的套路。如果我要查找数字4是否存在，则需要查出下标为0的数字，然后通过与运算符来判断第五位是否为1。

最终，上面的temp数组中的数字用2进制表示的话可能是这样的（64位太长了，用4位来表示）

[1000, 0001, 0011]

它实际表示，已经存在数字3，4，8，9。

也就是说，它就是用每一位的1来表示所对应的数字是否存在。

一些细节的解释：  
为什么是移6位？因为移6位相当于除以64，而64是长整形的长度。  
长整形每左移64位后值不变。`1l << i` 实际上相当于`1l << (i % 64)` 。

缺点：与桶排序一样，如果最大值过大，那么效率可能会很低。