题目一：找出数组中重复的数字

题目描述

在一个长度为n的数组里面所有的数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3。

方法一

先将数组排序，从重复的数组中找出重复的数字就比较容易。排序一个长度为n的数组需要时间O(nlogn)的时间。

public static void method1(int[] array){
  int[] sortAray = quicklySort(array, 0, array.length - 1);
  for (int i = 0; i < sortAray.length-1; i++) {
    if (sortAray[i] == sortAray[i+1]){
      System.out.println("method1 "+sortAray[i]);
     }
   } 
}
public static int[] quicklySort(int[] arr, int left, int right){
        int l = left; // 左下标
        int r = right; // 右下标
        // pivot 中轴值
        int pivot = arr[(l + r)/2];
        int temp = 0; //临时变量做交换时使用
        // while循环目的是让比pivot值小的放到左边
        // 比pivot值大的放到右边
        while (l < r){
            // 在pivot的左边一直找，找到大于等于pivot的值才退出
            while (arr[l] < pivot){
                l += 1;
            }
            // 在pivot的右边一直找，找到小于等于pivot的值才退出
            while (arr[r] > pivot){
                r -= 1;
            }
            // 如果l >= r 说明pivot的左右两的值，已经按照左边全部是
            // 小于等于pivot的值 右边全部都是大于等于pivot的值
            if(l >= r){
                break;
            }
            // 交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 如果交换完后 发现arr[l] == pivot值 相等 r-- 前移
            if (arr[l] == pivot){
                r -= 1;
            }
            // 如果交换完后 发现arr[r] == pivot值 相等 l++ 后移
            if (arr[r] == pivot){
                l += 1;
            }
        }
        // 如果l==r 必须要l++ r-- 否则为出现栈溢出
        if(l == r){
            l += 1;
            r -= 1;
        }
        // 向左递归
        if (left < r){
            quicklySort(arr,left,r);
        }
        // 向右递归
        if(right > l){
            quicklySort(arr,l,right);
        }
        return arr;
    }

方法二

可以通过哈希表来解决这个问题。从头到尾按顺序扫描数组中的每个数字，每扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表是否已经包含了该数字，如果还没有这个数字，就把他加入哈希表。如果哈希表里面已经存在该数字，就找到了一个重复的数字。时间复杂度为O(n)，但是空间复杂度为O(n)。

public static void method2(int[] array){
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsValue(array[i])){
                map.put(i,array[i]);
            }else {
                System.out.println("method2 "+array[i]);
            }
        }
    }

方法三

从头到尾依次扫描这个数组中的每个数字，当扫描到下表为i的数字时，首先比较这个数字用m表示是不是等于i。如果是，则接着扫描下一个数字；如果不是，则拿他再和第m个数字进行比较。如果他和第m个数字相等，就找到了一个重复的数字（该数字在下标i和m的位置都出现了）；如果他和第m个数字不等，就把第i个数字和第m个数字交换，把m放到属于它的位置。

public static void method3(int[] array){
        if (array.length <= 0){
            return;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i]<0||array[i]>array.length-1){
                return;
            }
        }
        int m;
        int temp;
        for (int i = 0; i < array.length; i++) {
            m = array[i];
            while (m != i){
                if (m == array[m]){
                    System.out.println(m);
                    break;
                }
                temp = array[m];
                array[m] = array[i];
                array[i] = temp;
            }
        }
    }