剑指Offer——不修改数组找出重复数字（C语言）

题目

给定一个长度为 n+1n+1 的数组nums，数组中所有的数均在 1∼n1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

数据范围

1≤n≤1000

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1)O(1) 的额外空间，该怎么做呢？

解题思路：

抽屉、分治

用二分法进行索引，看区间内的数字个数与区间中位数的大小关系
根据区间最后确定重复的数字

代码

int duplicateInArray(int *nums, int numsSize){  //数字下标：0~numsSize-1
    int l=1,r=numsSize-1;
    int i;
    while(l<=r)
    {
        int mid=(l+r)/2;  // 划分的区间：[l, mid], [mid + 1, r]
        int s=0;
        for(i=0;i<=numsSize-1;i++){
            if(*(nums+i)<=mid && *(nums+i)>=l) s++;
        }
        if(s>mid-l+1) r=mid;
        else l=mid+1;
    }
    return r;     //注意！！！返回的是r
}