整数数组arr大小为n，取值范围0~n-1，可能包含多个重复的数字，如果数组存在重复的数字，请找出数组arr中任意重复的数字。
思路1：使用哈希表，遍历arr，依次将arr[i]存入哈希表，如果哈希表中已经存在arr[i]，则表明arr[i]重复了。用这个方法，可以找出所有重复的数字，但是需要额外O(n)的空间，是以空间换时间。
思路2：直接修改arr数组，遍历arr，如果arr[i] != i,那么就进入一个循环，
如果arr[i] == arr[arr[i]]，则说明arr[i]出现了2次，是重复数字，可以返回了；
否则，就交换这两个数字，交换以后数字i就满足了arr[i] == i。
使用这个方法可以判断数组是否有重复数字，并且可以打印出一个重复数字，但是无法打印出所有的重复数字。
public class FindAnyDuplicateNumber {
public int getDuplicate(int[] numbers) {
if(numbers == null || numbers.length < 0){
return -1;
}
//边界条件，程序必须运行在正确的context下
for(int i = 0; i < numbers.length; i++){
if(numbers[i] <0 || numbers[i] > numbers.length){
return -1;
}
}
for(int i = 0; i < numbers.length - 1; i++){
while (numbers[i] != i){
if(numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
//swap numbers[i] numbers[numberp[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return -1;
}
public static void main(String[] args){
//只能找到一个重复的数字，如果要找到所有重复的数字，就要使用辅助数组
int[] nums = {1, 4, 2, 5, 2, 0, 6, 3};
System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums));
int[] nums2 = null;
System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums2));
int[] nums3 = {1, 4, 2, 5, 7, 0, 6, 3};
System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums3));
}
}
---------------------
作者：翁正存
来源：CSDN
原文：https://blog.csdn.net/Wengzhengcun/article/details/86359275
版权声明：本文为博主原创文章，转载请附上博文链接！
