描述：
在一個長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n-1 的范圍內(nèi)蜈缤。數(shù)組中某些數(shù)字是重復(fù)的踩窖，但不知道有幾個數(shù)字是重復(fù)的翘县，也不知道每個數(shù)字重復(fù)幾次诺擅。請找出數(shù)組中任意一個重復(fù)的數(shù)字市袖。
例子如下：
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
分析：
尋找數(shù)組中重復(fù)的數(shù)字，首先會想到的方法是遍歷一遍數(shù)組烁涌，然后記錄一下數(shù)組中每個元素出現(xiàn)的次數(shù)苍碟，若次數(shù)大于或等于2，則說明該元素重復(fù)撮执，這是使用暴力法來求解微峰。然而，這種情況下輔助數(shù)組的空間大量被浪費抒钱，導(dǎo)致空間復(fù)雜度非常高蜓肆。
分析題干颜凯，得到的信息是：數(shù)組中的元素的范圍是從0到n-1的，這樣說明利用數(shù)組中的元素的數(shù)值作為數(shù)組下標不會出現(xiàn)數(shù)組越界的現(xiàn)象仗扬。并且并不要求找到所有的重復(fù)元素症概，只需要找到任意一個重復(fù)元素即可。那么早芭，可以將數(shù)組中的每一個元素按照其數(shù)值放置到相應(yīng)的下標位置彼城，如果當某個元素出現(xiàn)重復(fù)時，這時該元素的數(shù)值所在的下標位置已經(jīng)有了相同大小的數(shù)值退个，這樣就可以確定重復(fù)的元素募壕。
接下來，將示例推導(dǎo)一遍如下：
- [2,3,1,0,2,5]
- 將元素2帜乞，放置到數(shù)組下標為2的位置司抱，將其與原始下標元素交換即可，得到[1,3,2,0,2,5]
- 將元素3黎烈，與數(shù)組下標為3的位置元素交換习柠，得到[1,0,2,3,2,5]
- 同理如下，當遍歷到數(shù)組下標為4時照棋，此時發(fā)現(xiàn)下標2位置的元素與下標4位置的元素數(shù)值相等资溃，說明這個元素重復(fù)
- 輸出重復(fù)元素2
實現(xiàn)代碼：
/**
這里要特別注意~返回任意重復(fù)的一個，賦值duplication[0]
*/
public static boolean duplicate(int numbers[],int length,int [] duplication) {
//判空處理
if (length<=1||numbers==null)
return false;
for (int i=0;i<length;i++){
//將值為i的元素不在為位置i上的元素開始交換
while (numbers[i]!=i){
//當數(shù)組元素的數(shù)值出現(xiàn)在對應(yīng)的下標位置烈炭，則說明該元素重復(fù)
if (numbers[i]==numbers[numbers[i]]){
duplication[0]=numbers[i];
return true;
}
swap(numbers,i,numbers[i]);
}
}
return false;
}
private static void swap(int[] nums, int a,int b){
int t=nums[a];
nums[a]=nums[b];
nums[b]=t;
}
