首页 / 面试 / 面试题3:数组中重复的数字
面试题3:数组中重复的数字
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了面试题3:数组中重复的数字,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1795字,纯文字阅读大概需要3分钟。
内容图文
![面试题3:数组中重复的数字](/upload/InfoBanner/zyjiaocheng/1039/ac3aba020e234d40b7cd6e9e5d6850c4.jpg)
1 题目:找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次,请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复得的数字2或者3.
2 思路
由于数组中的数字都在0~n-1 范围内,如果这个数组中没有重复的数字,那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字,有些位置可能存在多个数字,同时有些位置可能没有数字。
从头到尾扫描数组中的每个数字,当扫描到下标为i的数字时,首先比较这个数字(用m表示)是不是等于i。如果是,则接着扫描下个数字,若不是,则那它和第m个数字进行比较。若它和第m个数字相等,就找到一个重复的数字,如果它和第m个数字不相等,就把第i个数字和第m个数字交换,把m放到属于它的位置。重复操作,直至发现一个重复的数字。
3 示例代码
bool duplicate(int numbers[],int length,int* duplication)
{
if(length<=0 || numbers == nullptr)
{
return false;
}
for(int i = 0 ; i < length - 1 ; i++)
{
if(numbers[i]<0 || numbers[i]>length-1)
{
return false;
}
}
for(int i = 0 ; i < length; i++)
{
while(numbers[i] != i)
{
//代交换的数,是否与以该数字为下标的数组内容相等
if(numbres[i] == numbers[numbers[i]])
{
*duplication = numbers[i]
return true;
}else
{ // numbers[numbers[i]] 和 numbers[i] 交换位置
int temp = numbers[i];
numbers[i] = numbers[temp]
numbers[temp] = temp;
}
}
}
}
4 举例说明
以数组{2,3,1,0,2,5,3}为例分析,数组第0个数字为2,与它下标不相等,于是和小标为2的数字1交换,交换后{1,3,2,0,2,5,3}。此时第0个数字为1,仍旧交换,交换后为{3,1,2,0,2,5,3}。此时第一个数为3,和下标为3的数字0交换,交换后{0,1,2,3,2,5,3}。接下来下标0、1、2、3和数字都相等。不需任何操作,然后扫描第4个数字2,和下标不相等,然后准备和下标为2的数字交换,但此时它俩相等了。即数字2在下标4和下标2同时出现了。找到重复的数字了。
参考:
《剑指offer》
内容总结
以上是互联网集市为您收集整理的面试题3:数组中重复的数字全部内容,希望文章能够帮你解决面试题3:数组中重复的数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。