剑指offer:数组中重复的数字
题目一：找出数组中任意一个重复的数字
问题描述
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入输出
输入：[2,3,1,0,2,5,3]
输出：2或3
算法描述
方法一：预排序 + 扫描一遍
先把输入的数组排序。从排序的数值中找出重复的数字，只需要和相邻的数字进行比较是否相等，扫描一遍即可。
算法分析
方法二：哈希表
从头到尾扫描数组的每个数字，每扫描到一个数字，判断哈希表里是否已经包含了这个数字。如果哈希表里没有包含这个数字，就将它加入哈希表中。
算法分析
方法三：原地重排
注意到数组中的数字都在0~n-1的范围内。如果这个数组没有重复的数字，那么数字i就会对于下标i的位置；如果有重复数字，必然发生冲突。可以利用数字范围大小的特点，直接在原地重排。
思路：从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先判断数字是否等于i：
- 如果相等，继续下一个下标位置；
- 如果不相等，设numbers[i]=value，需和numbers[value]进行比较
- 如果相等，则说明之前已经有值为i的数字出现，所以有重复
- 如果不想等，交换这两个数numbers[value]和numbers[i]。（注意交换后，下标为i的位置仍然要继续判断）
算法分析
具体代码如下：
bool duplicate(int numbers[],int length,int* duplication){
if(numbers == nullptr || length < 0){
return false;
}
for(int i = 0;i<length;i++){
if(numbers[i]<0||numbers[i]>length-1)
return false;
}
for(int i = 0;i<length;i++){
while(numbers[i]!=i){
if(numbers[i]!=numbers[numbers[i]]){
// swap(numbers[i],numbers[numbers[i]])
int t = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = t;
}
else
*duplication = numbers[i];
return true;
}
}
return false;
}
题目二：不修改数组找出数组中任意一个重复的数字
问题描述
在一个长度为n+1的数字中，所有的数字都在1~n的范围内，所以数组至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
算法描述
方法一：
利用题目一的方法二 或 创建一个辅助数组，利用题目一的方法三修改辅助数组
算法分析
方法二：
我们把从1~ n 的数字从中间的数字middle分为两部分，前面一半为1 ~ middle，后面一半为middle + 1 ~ n。统计[1,middle]这个区间的整数在整个数组中出现的次数
- 如果次数超过m，那么该区间里一定包含了重复数字，则检验的数组目标就可以从[start,end]转变为[start,middle]，即end = middle
- 否则，后一半的区间里一定包含了重复数字，则检验的数组目标就可以从[start,end]转变为[middle+1,end]，即start = middle + 1
缩小了待检验区间的长度后，继续分两部分，直到找到一个重复的数字。整个过程类似二分查找。
算法分析
具体代码
int getDuplication(const int* numbers,int length){
if(numbers == nullptr || length <= 0)
return -1;
int start = 1;
int end = length-1;
while(end >= start){
middle = (end-start)>>1 + start;
int count = countRange(numbers,length,start,middle);
if(end == start){
if(count >1)
return start; //返回重复的数字
else
break;
}
if(count > (middle-start+1))
end = middle; //该区间start ~ middle中，有重复的数字，所以可以缩小区间范围从[start,end]变成[start,middle]
else
start = middle +1; //该区间start ~ middle中，没有重复的数字，则看后半区间
}
return -1;
}
int countRange(int* numbers,int length,int start,int end){
if(numbers == nullptr)
return 0;
int count = 0;
for(int i = 0;i<length;i++){
if(numbers[i]>=start && numbers[i]<=end)
count++;
}
return count;
}
参考资料：剑指offer 2.3.1 数组 面试题3：数组中重复的数字
|