題目描述
在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。
數組中某些數字是重複的,但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。
例如,如果輸入長度為7的數組{2,3,1,0,2,5,3},那麼對應的輸出是重複的數字2或者3。
思路
- 我們來思考一下,0~n-1 如果不重複是什麼情況,就是0~n-1這些數都有一個,排好序完全就是從小到大;如果存在重複,最後一個數肯定到不了n-1;
- i這個數的位置就在i這個位置,是以我們可以用調整位置,如果在這個位置上的數和i一樣,就說明有兩個i了呗
- hashset
代碼
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (numbers==null||numbers.length==)
{
return false;
}
HashSet<Integer> hashSet = new HashSet();
boolean flag = false;
for (int i = ; i < numbers.length; i++) {
if (hashSet.contains(numbers[i])) {
duplication[] = numbers[i];
flag = true;
}
else
hashSet.add(numbers[i]);
}
return flag;
}
public boolean duplicate1(int numbers[],int length,int [] duplication)
{
if (numbers==null||numbers.length==)
{
return false;
}
for (int i = ; i < numbers.length; i++) {
if (numbers[i]<||numbers[i]>numbers.length-)
return false;
}
for (int i = ; i < numbers.length; i++) {
while (numbers[i]!= i)
{
if (numbers[i] == numbers[numbers[i]])
{
duplication[] = numbers [i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp ;
}
}
return false;
}
收獲
- hashset
- 奇怪的位置鎖定