雅式机械加工网,志鸿优化设计答案网,好用的wordpress企业模版,旅行社网站规划与建设的流程图1 题目 不修改数组找出重复的数字
在一个长度为N1的数组里面的所有数字都在范围1~N范围内#xff0c;所以数组至少 有一个数字是重复的#xff0c;请找出重复数字#xff0c;但是不能修改输入的数组。 2 思路
思路1#xff1a;
我们开辟一个新的数组#xff0c;初始化…1 题目 不修改数组找出重复的数字
在一个长度为N1的数组里面的所有数字都在范围1~N范围内所以数组至少 有一个数字是重复的请找出重复数字但是不能修改输入的数组。 2 思路
思路1
我们开辟一个新的数组初始化为0然后把原始数组每个数据的值作为下标把新数组通过这个下标数据取出来如果取出来是1就说明这个下标数据重复了如果不是我们直接放进去然后进行新数组值进行操作。 思路2:
比如数据1 2 2 3 4 5 6 7 我们先找到中间的值(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 iostreamusing namespace std;int getCount(const int *a, int len, int start, int end)
{if (a NULL || len 0){return 0;}int count 0;for (int i 0; i len; i){if (a[i] start a[i] end){count;}}return count;
}int getResetNumber(const int *a, int len)
{if (a NULL || len 0){return -1;}int start 1, end len - 1;//int mid (end - start) / 2 start;while (end start){int mid (end - start) / 2 start;int count getCount(a, len, start, mid);if (end start){if (count 1){return start;}else{break;}}if (count (mid - start 1)){end mid;}else{start mid 1;}}return -1;
}int main()
{std::cout 请输入数组的长度 std::endl;int len 0;std::cin len;if (len 0){std::cout 数组的长度不合法 std::endl;return -1;}int *a new int[len];std::cout 请分别输入数组的每个数据 std::endl;for (int i 0; i len; i){std::cin a[i];if (a[i] 0 || a[i] len){std::cout 输入的数据有误 std::endl;return -1;}}//int count getCount(a, len, 1, len - 1);int value getResetNumber(a, len);if (value -1){std::cout 没有找到重复的数据 std::endl;return -1;}std::cout 其中一个重复的数据是 value std::endl;delete []a;return 0;
}89,1 Bot4 运行结果
请输入数组的长度
5
请分别输入数组的每个数据
1
2
3
4
2
其中一个重复的数据是2 5 本质和总结 在区间start~end里面我们要缩小一半区间我们直接找到start~end的中间数M (start - end) / 2 start然后遍历数组如果在这个范围的数据等于M 大于(M - start 1)说明这个段区间有重复数据反之数目重复数据在M1到end区间然后每次这切割以此类推所以这里要用到循环用循环就要条件我们知道二分法这些操作条件是while(end start),既然有循环那我们必须找到跳出循环条件的条件在while循环里面 if (end start) {辅助函数个数 1} else {break;}
