剑指offer之C语言不修改数组找出重复的数字

2023-08-28 22:49:04 77

1 题目

不修改数组找出重复的数字

在一个长度为N+1的数组里面的所有数字都在范围1~N范围内，所以数组至少有一个数字是重复的，请找出重复数字，但是不能修改输入的数组。

2 思路

思路1：

我们开辟一个新的数组，初始化为0，然后把原始数组每个数据的值作为下标，把新数组通过这个下标数据取出来，如果取出来是1，就说明这个下标数据重复了，如果不是，我们直接放进去，然后进行新数组值进行++操作。

思路2:

比如数据12234567，我们先找到中间的值(1+7)/2=4;然后我们判断数组里面每个元素1到4有多少个，如果有大于4个数的话，我们一定说明重复数据在范围1到4里面，反之在范围4到7中，比如我们上面的数据1到4有5个数据，我们说明可以知道重复数据范围是1到4，然后我们再把数据切一刀，从1到4，有点像二分法，以此类推，知道我们求出答案。

关键点：

1）我们要个辅助函数：需要知道数组中从范围start到end的元素个数

2）循环条件是while(end>=start)

3) 退循环条件是在while里面，if(end==start){通过辅助函数得到的个数大于1就返回这个start值}else{break;}

3 代码实现

#include
usingnamespacestd;
intgetCount(constint*a,intlen,intstart,intend)
{
if(a==NULL||len<=0)
{
return0;
}
intcount=0;
for(inti=0;i=start&&a[i]<=end)
{
++count;
}
}
returncount;
}
intgetResetNumber(constint*a,intlen)
{
if(a==NULL||len<=0)
{
return-1;
}
intstart=1,end=len-1;
//intmid=(end-start)/2+start;
while(end>=start)
{
intmid=(end-start)/2+start;
intcount=getCount(a,len,start,mid);
if(end==start)
{
if(count>1)
{
returnstart;
}
else
{
break;
}
}
if(count>(mid-start+1))
{
end=mid;
}
else
{
start=mid+1;
}
}
return-1;
}
intmain()
{
std::cout<<"请输入数组的长度"<>len;
if(len<=0)
{
std::cout<<"数组的长度不合法"<>a[i];
if(a[i]<=0||a[i]>=len)
{
std::cout<<"输入的数据有误"<
4 运行结果

请输入数组的长度

5

请分别输入数组的每个数据

1

2

3

4

2

其中一个重复的数据是2

5 本质和总结
在区间start~end里面，我们要缩小一半区间，我们直接找到start~end的中间数M=(start - end)/2+start，然后遍历数组，如果在这个范围的数据等于M 大于(M-start+1)说明这个段区间有重复数据，反之数目重复数据在M+1到end区间，然后每次这切割，以此类推，所以这里要用到循环，用循环就要条件，我们知道二分法这些操作条件是while(end>=start),既然有循环，那我们必须找到跳出循环条件的条件在while循环里面if(end==start){辅助函数个数>1}else{break;}
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接

剑指offer之C语言不修改数组找出重复的数字

热门推荐

随机推荐