本文首發(fā)于我的個(gè)人博客：尾尾部落
題目描述
在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)淘衙。 數(shù)組中某些數(shù)字是重復(fù)的扔涧，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字耗美。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}航缀，那么對應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2商架。
解題思路
最簡單的就是用一個(gè)數(shù)組或者哈希表來存儲已經(jīng)遍歷過的數(shù)字，但是這樣需要開辟額外的空間芥玉。
如果題目要求不能開辟額外的空間蛇摸，那我們可以用如下的方法：
因?yàn)閿?shù)組中的數(shù)字都在0~n-1的范圍內(nèi)，所以灿巧，如果數(shù)組中沒有重復(fù)的數(shù)赶袄，那當(dāng)數(shù)組排序后揽涮，數(shù)字i將出現(xiàn)在下標(biāo)為i的位置。現(xiàn)在我們重排這個(gè)數(shù)組饿肺，從頭到尾掃描每個(gè)數(shù)字蒋困，當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)，首先比較這個(gè)數(shù)字(記為m)是不是等于i敬辣。如果是雪标，則接著掃描下一個(gè)數(shù)字；如果不是溉跃，則再拿它和m 位置上的數(shù)字進(jìn)行比較村刨，如果它們相等，就找到了一個(gè)重復(fù)的數(shù)字（該數(shù)字在下標(biāo)為i和m的位置都出現(xiàn)了）喊积，返回true烹困；如果它和m位置上的數(shù)字不相等，就把第i個(gè)數(shù)字和第m個(gè)數(shù)字交換乾吻，把m放到屬于它的位置髓梅。接下來再繼續(xù)循環(huán)，直到最后還沒找到認(rèn)為沒找到重復(fù)元素绎签，返回false枯饿。
參考代碼
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 這里要特別注意~返回任意重復(fù)的一個(gè)，賦值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length == 0)
return false;
for(int i = 0; i < length; i++){
while(i != numbers[i]){
if(numbers[i] == numbers[numbers[i]]){
duplication[0] = numbers[i];
return true;
}else{
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
}
}
}
return false;
}
}
