题目一
在一个长度为n的数组里，所有数字都在0—n-1的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组｛2，3，1，0，2，5，3｝，那么对应的输出是重复的数字2或者3.
1 解法一 （借助辅助数组）
数组中元素只能取0—n-1之间的数字，如果我们新建一个长度为n的辅助数组，辅助数组的所有元素初始化时均为0，再遍历原数组，如果有数字m，则将辅助数组中下标为m的元素+1，这样，重复的数字，肯定在辅助数组中标记的个数大于1。
以数组｛2，3，1，0，2，5，3｝为例
辅助数组初始化为{0，0，0，0，0，0，0}
（1）、扫描下标为0的数字：
array[0]=2
标记辅助数组—>{0，0，1，0，0，0，0}
（2）、扫描下标为1的数字：
array[1]=3
标记辅助数组—>{0，0，1，1，0，0，0}
（3）、扫描下标为2的数字：
array[2]=1
标记辅助数组—>{0，1，1，1，0，0，0}
（4）、扫描下标为3的数字：
array[3]=0
标记辅助数组—>{1，1，1，1，0，0，0}
（5）、扫描下标为4的数字：
array[4]=2
标记辅助数组—>{1，1，2，1，0，0，0}
重复数字为2
public class Duplicate {
public static void main(String[] args) {
int[] array = {2, 3, 1, 0, 2, 5, 3};
System.out.println(duplicate(array));
}
private static int duplicate(int[] array) {
for(int i = 0; i < array.length; i++) {
while (array[i] != i) {
if(array[array[i]] == array[i]) {
return array[i];
}
int temp = array[array[i]];
array[array[i]] = array[i];
array[i] = temp;
}
}
throw new IllegalArgumentException();
}
}
这种解法时间的复杂度O(n)，空间的复杂度也是O(n)，解法二优化了空间复杂度
2 解法二 （重排数组）
数组中元素只能取0—n-1之间的数字，如果我们数组中每一个数字m放到数组下标为m的位置中，必定有某一个位置，不够放，这里，就是重复的数字。
实现的逻辑就是：重头到尾扫描数组，当扫描到下标为i的数字时，首先比较这个数字（用m表示）是不是等于i。如果是，则继续扫描，如果不是，则与数组中下标为m的数（array[m]）比较。如果array[m]与m不相同，就把array[m]与m交换，数字array[m]放到了下标为i的位置，m存放到了array[m]所在的位置，现在再重复判断下标为i的数字，知道下标为i的数值，存放的是i为止，然后再扫描下标为i+1的数字，执行同样的逻辑，这样，保证扫描过的下标都是存放数字本身。
以数组｛2，3，1，0，2，5，3｝为例
（1）、扫描下标为0的数字：
1： array[0]=2，2应该存放在array[2]中，2与array[2]比较（2与1），不同，切换位置
｛2，3，1，0，2，5，3｝——> ｛1，3，2，0，2，5，3｝
2： array[0]=1，1应该存放在array[1]中，1与array[1]比较（1与3），不同，切换位置
｛1，3，2，0，2，5，3｝——> ｛3，1，2，0，2，5，3｝
3： array[0]=3，3应该存放在array[3]中，3与array[3]比较（1与0），不同，切换位置
｛3，1，2，0，2，5，3｝——> ｛0，1，2，3，2，5，3｝
4： array[0]=0，0应该存放在array[0]中，扫描下标+1
（2）、扫描下标为1的数字：
array[1]=1，1应该存放在array[1]中，扫描下标+1
（3）、扫描下标为2的数字：
array[2]=2，2应该存放在array[2]中，扫描下标+1
（4）、扫描下标为4的数字：
array[3]=3，3应该存放在array[3]中，扫描下标+1
（5）、扫描下标为5的数字：
array[5]=2，2应该存放在array[2]中，2与array[2]比较（2与2），相同，说明数组中有二个2，得到重复数字2
public class Duplicate {
public static void main(String[] args) {
int[] array = {2, 3, 1, 0, 2, 5, 3};
System.out.println(duplicate(array));
}
private static int duplicate(int[] array) {
int[] temp = new int[array.length];
for(int i = 0; i < array.length; i++) {
if(temp[array[i]] != 0) {
return array[i];
} else {
temp[array[i]] = 1;
}
}
throw new IllegalArgumentException();
}
}
这种解法虽然有二重循环，但是每一个数字最多调换2次，时间的复杂度依然是O(n)，空间的复杂度变为O(1)，是通过改变数组来达到优化效果
题目二
在一个长度为n+1的数组里，所有数字都在1—n的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组｛2，3，1，4，2，5，3， 6｝，那么对应的输出是重复的数字2或者3.
ps:出这个题，只是为了提出怎么不改变数组，来找出重复的数字
解法一
扫描数组，分别计算0—n每个数出现的次数，明显我们可以得到我们想要的答案，时间复杂度为O(n2)，上代码
public class Duplicate {
public static void main(String[] args) {
int[] array = {2, 3, 1, 4, 2, 5, 3, 6};
System.out.println(duplicate(array));
}
private static int duplicate(int[] array) {
for(int i = 0; i < array.length - 1; i++) {
int count = 0;
for (int anArray : array) {
if (anArray == i) {
count++;
}
if (count > 1) {
return i;
}
}
}
throw new IllegalArgumentException();
}
}
这种解法时间复杂度太高，我们有另外一种优化的方式
解法二（不改变数组）
1—n，我们取中间数 middle = (n+1)/2，将数字分成二部分，前一半是1—middle，后一半是middle+1—n，所有的数字是0—n，有n种数字，而数组的大小是n+1，会存在一种情况，整个数组中，如果数字在1—middle范围内的个数如果大于middle+1，则重复的数字在1—middle范围内，否则，就在middle+1—n内，以此类推，我们再去划分1—middle为二部分，再去找重复的数字，知道找到重复的数字，这个过程和二份查找很类似。
public class Duplicate {
public static void main(String[] args) {
int[] array = {1, 3, 1, 4, 2, 5, 7, 6};
System.out.println(duplicate(array));
}
public static int duplicate(int[] array) {
if(array.length <= 2) {
throw new IllegalArgumentException();
}
int start = 1;
int end = array.length - 1;
while (start < end) {
int middle = (start + end) / 2;
if(count(array, start, middle) > middle - start + 1) {
end = middle;
} else {
start = middle + 1;
}
}
return start;
}
private static int count(int[] array, int start, int end) {
int count = 0;
for (int i: array) {
if(i >= start && i <= end) {
count++;
}
}
return count;
}
}
上述代码按照二份查找的思路，如果输入长度为n的数组，那么函数count将被调用O(logn)次，每次需要O(n)的时间，因此总的时间复杂度是O(nlogn)，空间复杂度是O(1)。这种算法不能保证找出所有重复的数字。例如，数组｛2，3，5，4，3，2，6，7｝，重复数字2不可能被找出，这是因为范围1—2内，没有1，2出现了二次，数字的个数与出现的个数一样。