题目一：找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
练习地址
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++
// 这里要特别注意~返回任意重复的一个，赋值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;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
题目二：不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字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;
}
复杂度分析
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(1)。
