题目一：找出数组中重复的数字
题目描述
在一个长度为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;
}
}
}
