題目一：找出數(shù)組中重復(fù)的數(shù)字
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2。
練習(xí)地址
https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
參考答案
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ù)的一個，賦值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 (numbers == null || length <= 0) {
return false;
}
for (int i = 0; i < length; i++) {
if (numbers[i] < 0 || numbers[i] > length - 1) {
return false;
}
while (numbers[i] != i) {
if (numbers[numbers[i]] == numbers[i]) {
duplication[0] = numbers[i];
return true;
} else {
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
}
return false;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)。
- 空間復(fù)雜度：O(1)。
題目二：不修改數(shù)組找出重復(fù)的數(shù)字
在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為8的數(shù)組{2,3,5,4,3,2,6,7}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3。
參考答案
public int getDuplication(int[] numbers, int length) {
if (numbers == null || length <= 0) {
return -1;
}
int start = 1, end = length - 1, mid;
while (start <= end) {
mid = (start + end) / 2;
int count = countRange(numbers, start, mid);
if (start == end) {
if (count > 1) {
return start;
} else {
return -1;
}
}
if (count > mid - start + 1) {
end = mid;
} else {
start = mid + 1;
}
}
return -1;
}
private int countRange(int[] numbers, int low, int high) {
int count = 0;
for (int number : numbers) {
if (number >= low && number <= high) {
count++;
}
}
return count;
}
復(fù)雜度分析
- 時間復(fù)雜度：O(nlogn)。
- 空間復(fù)雜度：O(1)。
