题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2
示例 2：

输入：nums = [3,1,3,4,2]
输出：3
示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解题

由于重复数的数量时不确定的，所以不能用投票法来做。又因为不能修改数组，所以排序和桶排都不能用。并且只能使用常量级 O(1) 的额外空间，所以不能使用哈希表。

暴力解法

直接遍历数组，统计每个数字出现的次数，如果某个数字出现的次数大于 1，则返回该数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findDuplicate(nums []int) int {
    for i := 1; i < len(nums); i++ {
        cnt := 0
        for j := 0; j < len(nums); j++ {
            if nums[j] == i {
                cnt++
            }
        }
        if cnt > 1 {
            return i
        }
    }

    return -1
}

这样空间复杂度是 O(1)，时间复杂度是 O(n^2)，不符合要求。提交后确实会超时。

二分查找

这里确实不太容易想到，由于数组中的数字都在 [1, n] 范围内，所以可以使用二分查找来解决这个问题。

这里关键是要想到数字和数量的关系。考虑到数组中的数字都是在 [1, n] 范围内的，并且有重复的数字，所以可以将数组分成两部分，左半部分是 [1, duplicate - 1]，右半部分是 [duplicate, n]。如果假设 duplicate 是重复的数字，那么整个数组中 [1, 2] 区间的数字个数为 2，[1, 3] 区间的数字个数为 3，[1, duplicate - 1] 区间的数字个数为 duplicate - 1。而 [1, duplicate] 区间的数字个数应该大于 duplicate，因为有重复的数字存在，同样 [1, duplicate + 1] 区间的数字个数也应该大于 duplicate + 1。

基于这个关系，就可以使用二分查找来二分 [1, n] 区间的数字。每次取中间值 mid，然后统计数组中小于等于 mid 的数字个数 cnt。如果 cnt <= mid，说明重复的数字在右半部分，否则在左半部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findDuplicate(nums []int) int {
	for left, mid, right := 1, len(nums)>>1, len(nums)-1; left <= right; mid = (right + left) >> 1 {
		cnt := 0
		for j := 0; j < len(nums); j++ {
			if nums[j] <= mid {
				cnt++
			}
		}

		if cnt <= mid {
			left = mid + 1
		} else {
			right = mid
			if left == right {
				return left
			}
		}
	}

	return -1
}

这里的时间复杂度是 O(n log n)，空间复杂度是 O(1)。提交后通过了所有测试用例。

Floyd 判圈算法（龟兔赛跑）

要想到这个方法，同样不容易。关键是要把这个数组看出一个有向有环图。比如第 i 个元素是 nums[i]，那么可以看成一个有向边 i -> nums[i]。由于数组中的数字都在 [1, n] 范围内，所以每个数字都可以看成一个节点。由于数组中有重复的数字，所以会形成一个环。算法之前在 142. 环形链表 II 中证明过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findDuplicate(nums []int) int {
    if len(nums) < 3 {
        return nums[0]
    }

    slow, fast := nums[0], nums[0]
	for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            slow = nums[0]
            for slow != fast {
                slow = nums[slow]
                fast = nums[fast]
            }
            return slow
        }
	}

	return -1
}

这里的时间复杂度是 O(n)，空间复杂度是 O(1)。提交后通过了所有测试用例。

总结

这里做了很多限制，关键就是要用到这个数组的特性，即数字都在 [1, n] 范围内，并且有重复的数字。然后就可以使用二分查找或者 Floyd 判圈算法来解决这个问题。二分查找的思路是通过统计小于等于中间值的数字个数来判断重复的数字在哪一半，而 Floyd 判圈算法则是将数组看成一个有向有环图，通过快慢指针来找到重复的数字。