【C/C++练习题】数组中重复的数字
《剑指Offer》面试题3
问题一、找出数组中重复的数字
题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，
那么对应的输出是重复的数字2或者3。
分析：数组的长度（n）等于数字的范围（0~n-1），如果使用数组下标来定位数组中数字的话，会出现两种情况
没有重复数字：每一个位置刚好对应一个数字，排序后的数组元素的值和下标一一对应
有重复数字：有些位置可能会出现多个数字，有些位置可能没有数字
算法思想：重排数组，把元素放置在指定的位置。通过遍历数组的每一个元素，
如果数组元素的值等于下标值，继续遍历下一个元素
如果数组元素的值不等于下标值，根据元素的值找到对应的位置，进行比较，再根据比较结果判断
比较值相等，找出重复数字，返回
比较值不等，进行位置交换
继续判断数组元素的值....
其他方法：
1.对数组排序，在已排序的数组中扫描重复数字
2.创建哈希表，通过判断新加入的数字在哈希表中是否已存在，来判断重复数字
代码
-
#include "iostream"
-
using namespace std;
-
-
-
//函数功能：寻找数组中的任意重复数字
-
//输入参数：numbers[] 源数组、length 数组长度、duplication 重复元素
-
//返回值： false 没有重复数字、true发现重复数字
-
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++)
-
{//1.遍历数组
-
-
while(i != numbers[i])
-
{//2.判断当前值是否等于下标值
-
if (numbers[i] == numbers[numbers[i]])
-
{//3.判断当前值是否已放置下标位置(判断存在)
-
*duplication = numbers[i]; //计入重复元素
-
return true; //4.已存在，返回结果
-
}
-
-
//5.交换当前值到下标位置
-
int temp = numbers[i];
-
numbers[i] = numbers[temp];
-
numbers[temp] = temp;
-
}
-
}
-
return false; //没有找到
-
}
-
-
-
//进行测试
-
void test01()
-
{
-
int numbers[] = {2, 3, 1, 0, 2, 5, 3};
-
int duplication = 0;
-
if ( duplicate(numbers, sizeof(numbers)/sizeof(int), &duplication) == true )
-
{
-
cout << "res:" << duplication << endl;
-
}
-
}
-
int main(int argc, char const *argv[])
-
{
-
test01();
-
return 0;
-
}
运行
问题二、不修改数组找出重复的数字
题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
分析：数组长度（n+1）大于数字的范围，所以一定有重复的数字。使用二分法的思路，将不断小查找区间的范围，对重复数字进行查找。
其他方法：创建一个辅助数组，在辅助数组中查找重复数字，不会破坏原数组的结构。
代码
-
#include "iostream"
-
-
using namespace std;
-
-
int countRange(const int* numbers, int length, int start, int end); //统计次数
-
int getDuplication(const int* numbers, int length); //查找任意重复数字
-
-
//功能:(已知)数组内有重复数字，查找重复数字
-
//输入:numbers源数组(数字范围1-n)、length数组长度(n+1)
-
//返回:重复的数字
-
int getDuplication(const int* numbers, int length)
-
{
-
if ( (numbers == nullptr) || (length <= 0) )
-
{//无效参数
-
return -1;
-
}
-
-
int start = 1;
-
int end = length - 1;
-
-
while(start <= end)
-
{
-
//1.将数字序列所在区间进行二分
-
int middle = (end - start)/2 + start;
-
-
//2.统计区间范围的数字的出现次数
-
int count = countRange(numbers, length, start, middle);
-
-
//3.判断区间长度是否为1，找出重复数字
-
if (start == end)
-
{
-
if (count > 1)
-
{
-
return start;
-
}
-
else
-
{
-
break;
-
}
-
}
-
-
//4.重新调整区间，区间内包含重复数字
-
if ( count > ((middle - start) + 1) )
-
{
-
end = middle;
-
// end = middle - 1;
-
}
-
else
-
{
-
start = middle + 1;
-
}
-
-
}
-
return -1;
-
-
}
-
-
-
//功能：统计start-end范围的数字的出现次数
-
//输入：numbers源数组、length数组长度、start，end表示数字范围
-
int countRange(const int* numbers, int length, int start, int end)
-
{
-
if ( (numbers == nullptr) || (length <= 0) )
-
{//无效参数
-
return 0;
-
}
-
-
int count = 0;
-
for (int i = 0; i < length; i++)
-
{//遍历数组元素
-
if ( (start <= numbers[i]) && (numbers[i] <= end) )
-
{
-
count++; //统计次数
-
}
-
}
-
return count;
-
}
-
-
void test01()
-
{
-
int arr[] = {2, 3, 5, 4, 3, 2, 6, 7};
-
int res = getDuplication(arr, sizeof(arr)/sizeof(int));
-
cout << "res:" << res << endl;
-
}
-
-
int main(int argc, char const *argv[])
-
{
-
test01();
-
return 0;
-
}
运行
总结：面试官提出的需求不同，最终所采用的算法也不相同，这说明面试中和面试官的交流的重要性！！
我的码云：https://gitee.com/hinzer/sword_to_offer/tree/master/questions
文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/feit2417/article/details/96566093
- 点赞
- 收藏
- 关注作者
评论（0）