编写一个程序给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。 请找出数组中任意一个重复的数字。

以下是 Python 代码：

def duplicateInArray(nums):
  for i in range(len(nums)):
    if nums[i] != i:
      if nums[i] == nums[nums[i]]:
        return nums[i]
      else:
        temp = nums[i]
        nums[i] = nums[temp]
        nums[temp] = temp
  return -1

该算法的时间复杂度为 O(n)。

算法的思路如下：

1. 对于数组中的每个数字 nums[i]，如果 nums[i] ≠ i，则将 nums[i] 放到它应该在的位置 nums[i]。
2. 如果 nums[i] = nums[nums[i]]，说明 nums[i] 和 nums[nums[i]] 重复了。
3. 如果 nums[i] ≠ nums[nums[i]]，则交换 nums[i] 和 nums[nums[i]]。
4. 重复步骤 1~3，直到找到重复的数字或者所有的数字都在正确的位置上。

这种算法的正确性在于，对于每个数字 nums[i]，如果它不在它应该在的位置 nums[i]，那么一定会被放到它应该在的位置。当所有的数字都在正确的位置上时，如果有重复的数字，则必定会有 nums[i] = nums[nums[i]]。

相关问题

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

方法一：哈希表

使用一个哈希表，遍历数组中的每个数，如果该数不在哈希表中，则将其加入哈希表，否则说明该数重复，直接返回即可。

时间复杂度：O(n)

空间复杂度：O(n)

方法二：二分查找

对于数组中的元素，由于它们的值都在 1∼n 的范围内，因此可以将数组划分为若干个区间，每个区间的值范围都是 [left, mid] 或 [mid+1, right]。如果整个数组中没有重复的元素，那么整个数组中的元素个数就是 n，而每个区间的元素个数都是 (mid - left + 1) 或 (right - mid)。

由于题目保证了数组中一定有重复的元素，因此可以通过统计整个数组中小于等于 mid 的元素的个数，进而判断重复元素在哪个区间中。假设整个数组中小于等于 mid 的元素个数为 count，如果 count 严格大于 mid，那么重复元素就在区间 [left, mid] 中；否则重复元素在区间 [mid+1, right] 中。这个思路类似于二分查找。

时间复杂度：O(nlogn)

空间复杂度：O(1)

代码实现：

方法一：

def findDuplicate(nums: List[int]) -> int:
    num_set = set()
    for num in nums:
        if num in num_set:
            return num
        num_set.add(num)

方法二：

def findDuplicate(nums: List[int]) -> int:
    n = len(nums)
    left = 1
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        count = 0
        for num in nums:
            if num <= mid:
                count += 1
        if count > mid:
            right = mid
        else:
            left = mid + 1
    return left

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)。