在一个整数数组中，有一个重复的数字，如何找到重复数字？(请用代码实现)

这个是面试一家给我的笔试题，这个题我是用双重for循环循环遍历得到重复的数据，面试官问我时间复杂度是多少，我说是O(n^2)；我知道这种实现效率不高，查询比较慢的，公司工作不忙搜索了一下还可以用别的怎么实现，我看它上面的思路以后自己写的，没按照它给的示例写，但是测试效率以后发现是比我之前写的双重for循环查询的很快。它的思路是这样的。

思路

　　从哈希表的思路拓展，重排数组：把扫描的每个数字（如数字m）放到其对应下标（m下标）的位置上，若同一位置有重复，则说明该数字重复。

题目上面还写了数组的范围：

1.整数在1..n范围内

2.数组的长度是n+1

我的实现方式是定义一个临时数组，将整型数字数组作为下标存储，如果遍历发现当前下标被存储了数据，就说明当前元素是重复的值，输出即可，代码如下

   public static void checkRepeat(int[] nums) {
        int[] tempList = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < nums.length) {
                if (tempList[nums[i]] == 0) {
                    tempList[nums[i]] = nums[i];
                } else {
                    System.out.println("重复数字为:" + nums[i]);
                }
            }

        }
    }

测试main方法

 public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] nums1 = {1, 2, 3, 2,4, 5, 5};
        checkRepeat(nums1);
        System.out.println("耗时:" + (System.currentTimeMillis() - start) + "ms");
    }

咱们接下来要测试一下查询性能，随机10万个数，用以上的方法，和我之前写的双重for循环来测试看哪个查询更快。

public static void main(String[] args) {
        int[] nums = new int[100000];
        Random rand = new Random();
        for (int i = 0; i < 100000; i++) {
            nums[i] = rand.nextInt(999991);
        }
        long start = System.currentTimeMillis();
        checkRepeat(nums);
        System.out.println("耗时:" + (System.currentTimeMillis() - start) + "ms");
    }

用时15ms,10万条数据

双重for循环的来测试一下

    public static void main(String[] args) {
        int[] nums = new int[100000];
        Random rand = new Random();
        for (int i = 0; i < 100000; i++) {
            nums[i] = rand.nextInt(999991);
        }
        long start = System.currentTimeMillis();
        checkRepeat1(nums);
        System.out.println("耗时:" + (System.currentTimeMillis() - start) + "ms");
    }

  public static void checkRepeat1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    System.out.println("重复数字为:" + nums[i]);
                }
            }
        }
    }

用时5237ms，哇塞，输了输了

用这种方式就是空间换时间，也只用遍历n次，所以就是O(n)