C语言代码实现给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1 。 请找出数组中任意一个重复的数，但不能修改输入的数组。

这道题可以使用二分查找和桶排序两种方法来解决，下面分别介绍：

1. 二分查找

我们可以按照二分查找的思路，将数组中的数按照大小分为两部分，统计其中小于等于中间值的数的个数，如果个数大于中间值，则说明重复数在左半部分，否则在右半部分。然后不断缩小查找范围，直到找到重复数。

具体实现如下：

int findDuplicate(int* nums, int numsSize){
    int left = 1, right = numsSize - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        int count = 0;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] <= mid) {
                count++;
            }
        }
        if (count > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

2. 桶排序

我们可以开一个桶，将每个数放入对应的桶中，如果某个桶中已经有数了，则说明这个数重复了，直接返回即可。由于数组中的数都在 1~n 的范围内，所以一共只需要 n 个桶即可。

具体实现如下：

int findDuplicate(int* nums, int numsSize){
    int bucket[numsSize];
    memset(bucket, 0, sizeof(bucket));
    for (int i = 0; i < numsSize; i++) {
        if (++bucket[nums[i]] > 1) {
            return nums[i];
        }
    }
    return 0;
}

时间复杂度为 O(n)，空间复杂度为 O(n)。