算法练习第十题——寻找重复数(不修改数组)

算法练习第十题——寻找重复数(不修改数组)

寻找重复数(不修改数组)题目

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

注意： 你设计的解决方案必须 不修改 数组 nums

示例一：

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

输出： 1

示例二：

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

输出： 4

示例三：

输入： nums = [0,1,5,4,0]

输出： 0

解题思路

方法一：二分查找

我们定义 cnt[i] 表示 nums 数组中小于等于 i 的数有多少个，假设我们重复的数是 target，那么 [1,target−1]里的所有数满足 cnt[i]≤i，[target,n] 里的所有数满足 cnt[i]>i，具有单调性。

以下代码以golang为例子：

func findDuplicate(nums []int) int {
    n := len(nums)
    l, r := 1, n - 1
    ans := -1
    for l <= r {
        mid := (l + r) >> 1
        cnt := 0
        for i := 0; i < n; i++ {
            if nums[i] <= mid {
                cnt++
            }
        }
        if cnt <= mid {
            l = mid + 1
        } else {
            r = mid - 1
            ans = mid
        }
    }
    return ans
}

该解法复杂度分析

• 时间复杂度：O(nlogn)，其中 n 为 nums 数组的长度。

• 空间复杂度：O(1)。
• 
  

方法三：快慢指针

我们对 nums 数组建图，每个位置 i 连一条 i→nums[i] 的边。由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口，那么整个问题就等价于环形链表。

func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] { }
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

该解法复杂度分析

• 时间复杂度：O(n)O(n)。「Floyd 判圈算法」时间复杂度为线性的时间复杂度。

• 空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。