287. 寻找重复数

LeetCode 287¹ · 中等 · 技巧

题

长度为 n + 1 的数组，元素都在 [1, n] 内，恰有一个值重复（可能重复多次），找出它。要求不修改数组、只用 \(O(1)\) 额外空间。

例：nums = [1, 3, 4, 2, 2] → 2；nums = [3, 3, 3, 3, 3] → 3。

一句话

从下标 0 出发沿 i → nums[i] 走，一定会进环；有两个下标指向同一个值，那个值就是环入口——用环形链表 II 的找入口法。

关键技巧

建模成函数图。 把下标 i 看成节点、nums[i] 看成它的 next。值域是 [1, n]，所以没人指向 0——0 只能是链的起点，不在环上。\(n + 1\) 个节点、每个出度为 1，从 0 出发必然进环。

为什么入口就是重复值。 环入口是「被两个不同节点指向」的节点：一个来自环外的链、一个来自环内的前驱。被两个下标指向 ⇔ 这个值出现了两次以上。

Floyd 两阶段。

1. 快指针一次两步、慢指针一次一步，从 0 出发，在环内相遇。
2. 一个指针回到 0，两个都一次一步，再次相遇处就是入口。

第二阶段的证明：设起点到入口距离 \(a\)，入口到相遇点 \(b\)，环长 \(c\)。相遇时快指针走的步数是慢指针的两倍：\(2(a+b) = a + b + kc\)，得 \(a = kc - b\)——从相遇点再走 \(a\) 步恰好绕回入口。

另一个 O(1) 解：值域二分。 猜答案 \(\le m\)：统计数组里 \(\le m\) 的个数 cnt，鸽巢原理下 cnt > m 说明重复值在 \([1, m]\) 里。\(O(n\log n)\)，不改数组，思路更直接。

为什么排除别的做法。 排序、原地标负号都改数组；哈希集合 \(O(n)\) 空间。

解

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0
        while True:                      # 阶段一：环内相遇
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = 0
        while slow != fast:              # 阶段二：同速走到入口
            slow = nums[slow]
            fast = nums[fast]
        return slow

class Solution2:
    def findDuplicate(self, nums: List[int]) -> int:
        lo, hi = 1, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if sum(x <= mid for x in nums) > mid:  # [1, mid] 里挤了太多数
                hi = mid
            else:
                lo = mid + 1
        return lo

延伸

• 原型：142. 环形链表 II，这里只是把链表换成了数组映射；判环本身见 141. 环形链表。
• 「值域 [1, n] ⇒ 下标即哈希」同一招：41. 缺失的第一个正数 允许改数组，就原地交换归位。
• 坑：必须从下标 0 出发——0 保证不在环上；从别的下标出发，阶段二的「回到起点」可能本身就在环里，找到的不一定是重复值。

import random as _r
for S in (Solution, Solution2):
    s = S()
    for arr, want in [
        ([1, 3, 4, 2, 2], 2),
        ([3, 1, 3, 4, 2], 3),
        ([3, 3, 3, 3, 3], 3),
        ([1, 1], 1),
        ([2, 5, 9, 6, 9, 3, 8, 9, 7, 1], 9),
    ]:
        before = arr[:]
        assert s.findDuplicate(arr) == want
        assert arr == before  # 不改数组
    for _ in range(200):
        n = _r.randint(1, 30)
        dup = _r.randint(1, n)
        arr = list(range(1, n + 1)) + [dup]
        _r.shuffle(arr)
        assert s.findDuplicate(arr) == dup