让人瑟瑟发抖的面试题
。
。
。

来我们看一下题目
在一个 长度为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;}

总结：在不修改数组的情况下，只要知道数组元素范围，就可以通过二分元素的方法，找到重复的数字