让人瑟瑟发抖的面试题
.
.
.
来我们看一下题目
在一个 长度为 n+1 的数组里的所有数字都在 1~n 的范围内, 所以数组中至少有一个数字是重复的. 请找出数组中任意一个重复的数字, 但不能修改输入的数组.
注意: 时间复杂度 O(n), 空间复杂度 O(1)
找出数组中重复的数字 (c 语言) 怎么解决勒???
分析: 利用题目中元素处于 1~n 的范围, 把元素分为两组, 判断两组元素个数, 如果大于范围, 则重复的数字就在这个范围内. 例如: 1~3 范围中有 4 个数, 说明其中至少有一个重复的数字. 按此二分下去, 将会剩下一个数字有两个, 最后输出.
来看看代码
- #include<stdio.h>
- #define SIZE(arr) sizeof(arr)/sizeof(arr[0])// 数组长度
- int count_r(const int *arr,int start, int end,int len)// 元素范围内元素的个数
- {
- int count = 0;
- int i = 0;
- for (; i <len; i++)
- {
- if (arr[i]>= start&&arr[i] <= end)
- {
- count++;
- }
- }
- return count;
- }
- int duplicate1(const int *arr, int len)
- {
- if (len <0)
- {
- return 0;
- }
- int start = 1, end = len - 1;
- int count = 0;
- while (end>= start)
- {
- int mid = ((end - start)>> 1) + start;// 元素中值
- count = count_r(arr,start, mid,len);// 元素二分后, 其中一组元素范围的个数
- if (count>(mid - start + 1))// 确定元素范围
- {
- end = mid;
- }
- else
- {
- start = mid+1;
- }
- if (end == start)// 确定元素定位到一个元素
- {
- if (count> 1)
- return start;
- else
- break;
- }
- }
- return 0;
- }
- int main()
- {
- int arr[] = { 2, 3, 5,4,3,2,6,7 };
- printf("%d", duplicate1(arr, SIZE(arr)));
- return 0;
- }
总结: 在不修改数组的情况下, 只要知道数组元素范围, 就可以通过二分元素的方法, 找到重复的数字
不修改数组找出重复的数字(c 语言)
来源: http://www.bubuko.com/infodetail-3190226.html