在一个包含40亿个随机排列的32位整数的顺序文件中（注意随机排序），找出一个不再文件中的32位整数

浅浅的花香味﹌ 2022-10-01 00:48 89阅读 0赞

#### 完整的题目： ####

在一个包含40亿个随机排列的32位整数的顺序文件中（注意随机排序），找出一个不再文件中的32位整数（即int类型的整数），

文件中至少缺少一个这样的数

#### 要求： ####

使用最少的内存，可使用外部的临时文件

#### 思路： ####

将每个数转换为2进制数，然后进行0/1探测，将为0的位保存在一个文件中，将为1的位保存在另一个文件中，

一个文件中至多只有20亿个，因为40亿小于2的32次方，所以缺少的肯定很多，题目要求只要找到1个即可，

书里面翻译有误导性，我们应该以含有整数最少的文件再次作为数据源，进行0/1探测，

这次探测的是第二位（从左至右）再进行分类，依次类推 这样算法时间复杂度只有O(n);

#### 不足： ####

这样的思路只能找到一个数，如果需要都找到所有缺少的数且内存充足的情况下应该考虑位图排序

#### 可行性： ####

我们以0～15为范围，这些数最多只占4比特，15对应的二进制为1111，如果少8，8对应的二进制为1000，

将0～15这些书按高位0/1分为两份，这样最高位为1就会比最高位为0的数的个数少，这样就可以断定缺少的数的高位

一定是和较少数的高位是一样的，然后再对数量少的那一份进行第二位的0/1探测再次划分两份，依次类推

#### 代码： ####

这里我用两个List代替了临时文件，完整代码如下：

public class FindLackNumber {
    
    	private static int bit = 4;// 总共的位数，int 32位,这里为了方便举例，数字最大为15只占四位
    
    	private static Integer[] temp;
    	private static List<Integer> zero;// 存放0
    	private static List<Integer> one;// 存放1
    	private static int number;
    
    	// 找到数组a中缺少的整数
    	public static int find(Integer[] a) {
    		temp = a;
    		zero = new ArrayList<>();
    		one = new ArrayList<>();
    
    		while (bit-- > 0) {
    			zero.clear();
    			one.clear();
    			for (int i = 0; i < temp.length; i++) {
    				// 高位为1
    				if ((temp[i] & (1 << bit)) != 0) {
    					one.add(temp[i]);
    				} else {
    					zero.add(temp[i]);
    				}
    			}
    
    			if (zero.size() < one.size()) {
    				temp = (Integer[]) zero.toArray(new Integer[zero.size()]);
    //				number |= 0 << bit;
    			} else {
    				temp = (Integer[]) one.toArray(new Integer[one.size()]);
    				number |= 1 << bit;
    			}
    		}
    		return number;
    
    	}
    
    	public static void main(String[] args) {
    		Integer[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15 };
    		System.out.println(find(a));
    
    	}
    
    }