空间换时间案例—最快速度求0-9999顺序打乱中缺失和重复的数和2020年

---

一、问题

题目的思想 ：拿时间换空间， 拿空间换时间
        题： 有一个容器， 里面存储了1万个 连续的数 0-9999 (数的顺序是打乱的) ， 但是这些数组里面 其中一个数 是缺失的， 有一个数 是重复的。
            比如： 0 1 2 3 7 5 6 7 8 9  -- 7 是重复的 4是缺失的。
            顺序乱的： 9 6 7 3 2 7 5 1 0 8    -- 7 是重复的 4是缺失的。
            请你 用最快速的方法， 找到 那个缺失的数， 找到那个重复的数。

二、代码

import java.util.*;

public class Demo3 {
    public static void main(String[] args) {
        Integer[] intArr = getIntArr(10000);
        int[] newIntArr = new int[intArr.length];
        for (int i = 0; i < intArr.length; i++) {
            newIntArr[intArr[i]]++;
        }
        for (int i = 0; i < newIntArr.length; i++) {
            if (newIntArr[i] == 0) {
                System.out.println("查找的缺失的值是：" + i);
            } else if (newIntArr[i] == 2) {
                System.out.println("查找的重复的值是：" + i);
            }
        }
    }

    private static Integer[] getIntArr(int len) {
        Random r = new Random();
        LinkedList<Integer> intList = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            intList.add(i);
        }
        int repNum = 0;
        int loserNum = 0;
        while (true) {
            repNum = r.nextInt(len);
            loserNum = r.nextInt(len);
            if (!(repNum == loserNum)) {
                break;
            }
        }
        intList.set(loserNum, repNum);
        System.out.println("生成的缺失数是：" + loserNum);
        System.out.println("生成的重复数是：" + repNum);

        Collections.shuffle(intList);
        Integer[] intArr = intList.toArray(new Integer[intList.size()]);
        return intArr;
    }
}

生成的缺失数是：4951
生成的重复数是：4466
查找的重复的值是：4466
查找的缺失的值是：4951

---

本文地址：https://blog.csdn.net/weixin_46006988/article/details/110295892