天涯红月c++实现数组中的重复数字+不改变数组的重复数字的⼆分查法 题⽬描述：出数组中重复的数字
⾸先说明：不同的要求使⽤的函数是不⼀样的，如果只要求判断数组是否含有重复数字，并出其中的任意⼀个可以使⽤下⾯的两种⽅法，如果出每⼀个出现的重复数字还是得进⾏排序，遍历。
在⼀个长度为n的数组中，所有数字都在0~n-1的范围内，数组中某些数字是重复的，但不知道有⼏个数字重复了，也不知道每个数字重复了⼏次，请出数组中任意⼀个重复数字，如输⼊长度为7的数组arr[]={2,3,1,0,2,5,3}，那么对应输出是重复数字2,3
分析：简单的⽅法就是对数组整个进⾏sort排序，然后for循环遍历数组，如果前后两个数相等那么这个数组就有重复数字。
如果数组的前提的数字范围在0~n-1的范围内，在不⽤排序算法的前提下可以使⽤下列⽅法：
看数组中的第i个数m，如果i!=m说明m是不属于排序后i这个坑的，那么就到m的坑也就是数组中的第m个值，如果第m个值不等于m，则交换两个值，如果相等则说明他就是那么重复值，说到这⾥可能还是很模糊的概念，那么我们来具体画⼀下数组重排图解：
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]]){
*duplication=numbers[i];
return true;
}
int temp=numbers[i];
numbers[i]=numbers[temp];
numbers[temp]=temp;
}
}
return false;
}
以上代码来⾃剑指offer，亲测有效，下⾯来说明⼀下代码实现的功能：
1. ⾸先代码的返回值是bool类型变量，如果返回true说明原数组中有重复数字，反之没有； 2. 代码中第⼀个参数是需要重排的数组，第⼆个参数是数组的长度，第三个参数是我们返回的出现重复的数字，使⽤⽅法：我们可以在
调⽤的时候先定义⼀个int duplication；调⽤的时候： duplicate(arr,7,&duplication)；
3. 这个函数只能返回⼀个重复的数字。
4. 代码的时间复杂度为O(n)。
如果我们在题⽬中要求不可以改变数组呢？
最容易想到的⽅法就是我们创建⼀个辅助数组，在遍历数组的同时将数据复制到辅助数组中，需要O(n)的辅助空间，在不需要辅助空间的情况下可以使⽤如下办法： 题⽬描述：在⼀个长度为n+1的数组中所有数字都在1~n的范围内，所以数组中⾄少有⼀个数字是重复的。请出数组中任意⼀个重复数字，但不能修改输⼊的数组，例如，如果输⼊长度为8的数组arr[]={2,3,5,4,3,2,6,7}，那么对应的输出是重复数字2或者3。
1. 把1~n的数字从中间的数字m分为两部分，前⾯⼀半为1–m，后⾯⼀半为m+1–n。
2. 如果1~m的数字的数⽬超过m，前半段区间⾥⼀定包含重复的数字。
3. 否则另⼀半包含重复的数组。
以上述数组为例：
把数组分为1–4的部分和5–8的部分，1–4的部分数字出现了5次，则在这⼀部分⼀定有重复数字，同样再分为1–2和3–4的部分，1–2的部分数字出现了2次，不⽤管，3–4的部分出现3次，则重复数字就在这两个数字中出现
代码如下：
int countRange(const int* numbers, int length, int start, int end); int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;
int start = 1;
int end = length - 1;
while(end >= start)
{
int 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;
else
start = middle + 1;
}
return -1;
}
int countRange(const int* numbers, int length, int start, int end) {
if(numbers == nullptr)
return 0;
2011江苏高考语文
int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
盐酸纳洛酮
++count;
return count;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议