题目出处
- 剑指 Offer - 3 - 数组中重复的数字
数组中重复的数字
1 题目描述
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，那么对应的输出是重复的数字 2 或者 3。
2 解题思路
思路一：排序
先排序，然后扫描相邻数字是否相同。但是排序时间复杂度为 O(nlogn)
思路二：辅助空间
扫描数组，用哈希表记录重复数字，时间复杂度 O(n)，空间复杂度 O(n)
思路三：原位替换
因为数组中的数字都在 [0, n-1] 范围内，可以将值为 i 的元素调整到第 i 个位置上。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。
时间复杂度 O(N)，空间复杂度 O(1)。
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(null == numbers || length <= 0){
return false;
}
for(int i = 0; i < length; i++){
while(numbers[i] != i){
int value = numbers[i];
if(numbers[i] == numbers[value]){
duplication[0] = value;
return true;
}
swap(numbers, i, value);
}
}
return false;
}
private void swap(int numbers[], int i, int j){
numbers[i] = numbers[i] + numbers[j];
numbers[j] = numbers[i] - numbers[j];
numbers[i] = numbers[i] - numbers[j];
}
}
不修改数组找出重复的数字
1 题目描述
在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但是不能修改输入的数组。
例如，如果输入长度为 8 的数组 {2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字 2 或者 3。
2 解题思路
思路一：辅助空间
由于不能修改输入的数组，我们可以创建一个长度为 n+1 的辅助数组，然后逐一把原数组的每个数字复制到辅助数组。
如果原数组中被复制的数字是 m，则把它复制到辅助数组中下标为 m 的位置。如果下标为 m 的位置上已经有数字了，则说明该数字重复了。
由于使用了辅助空间，故该方案的空间复杂度是 O(n)。
思路二：时间换空间
避免使用辅助空间。如果数组中有重复的数，那么 n+1 个 0~n 范围内的数中，一定有几个数的个数大于 1。
按照二分查找的思路，将 1~n 的数字从中间的数字 m 分为两部分，前面一半为 1~m，后面一半为 (m+1)~n。
如果 1~m 的数字的数目大于 m，那么这一半的区间一定包含重复的数字；否则，另一半 (m+1)~n 的区间里一定包含重复的数字。
我们可以继续把包含重复数字的区间继续二分，直到找到一个重复的数字。
这种算法不能保证找到所有重复的数字。
如果输入长度为n的数组，那么函数 countRange 最多将被调用 O(logn) 次，每次需要 O(n) 的时间，因此总的时间复杂度是 O(nlogn)。但是如果区间无重复的数，则时间复杂度将变为 O(n2)。
public class Solution {
public int getDuplication(int[] arr, int length){
if(null == arr || length <= 0){
return -1;
}
int start = 0;
int end = length - 1;
while(end >= start){
int middle = ((end - start) >> 1) + start;
int count = countRange(arr, length, start, middle);
if(end == start){
if(count > 1){
return start;
}else{
break;
}
}
if(count > (middle - start + 1)){
end = middle;
}else{
start = middle + 1;
}
}
return -1;
}
private int countRange(int[] arr, int length, int start, int end){
if(null == arr){
return 0;
}
int count = 0;
for(int i = 0; i < length; i++){
if(arr[i] >= start && arr[i] <= end){
++count;
}
}
return count;
}
}