数组中重复的数字：
题目来源
牛客网
题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
解题思路:
第一种解法：判断数组中元素是否重复？首先的想法就是获取数组第一个位置的元素，然后从第二个开始遍历，判断后续的数组中是否有元素与当前的元素一致… 然后一致循环下去：时间复杂度：O(n^2)
public class Solution {
public boolean duplicate(int numbers
[],int length
,int [] duplication
) {
for(int i
= 0;i
<length
;i
++){
for(int j
= i
+ 1;j
< length
;j
++){
if(numbers
[i
] == numbers
[j
]){
duplication
[0] = numbers
[i
];
return true;
}
}
}
return false;
}
}
第二种解法：由于数组的长度为n，且其中的所有数字全部都在n-1的范围之内，所以也就是说如果没有重复的数字，每个索引位置都存放着与当前索引相同的数字 即：如果数组的长度为4，那么数组中没有重复元素数组应当为[0,1,2,3]。可以由此来进行判断，首先遍历数组，获取每个索引位置的数字，与当前索引元素的时间复杂度 O(n)
public class Solution {
public boolean duplicate(int numbers
[],int length
,int [] duplication
) {
for(int i
= 0;i
< length
;i
++){
while(i
!= numbers
[i
]){
if(numbers
[i
] == numbers
[numbers
[i
]]){
duplication
[0] = numbers
[i
];
return true;
}
swap(numbers
,i
,numbers
[i
]);
}
}
return false;
}
private void swap(int[] numbers
,int i
,int j
){
int temp
= numbers
[j
];
numbers
[j
] = numbers
[i
];
numbers
[i
] = temp
;
}
}
简单来说就是数组的长度为5，数组元素没有重复正常应该为[0,1,2,3,4] 遍历数组，第一个下标判断值是否为0，如果不为0，将该元素与numbers[numbers[0]] 交换位置，然后再次判断是否与当前下标符合… 但是如果在此交换的过程中 如果发现被交换元素与交换元素相等，则返回该元素。
