0287. Find the Duplicate Number

题目信息

题号:

0287

难度:

Medium

主题:

数组、重复值、只读输入、常数空间

原题:

LeetCode 0287

重点:

长度为 n+1 而取值只有 1..n、唯一重复值可出现多次、不能修改数组

题目重述

给定包含 n+1 个整数的数组 nums,每个元素都位于 [1, n]。题目保证只有一个不同的整数在数组中重复出现,但这个整数可能出现两次,也可能出现更多次。返回这个唯一的重复值。

1 <= n <= 10^5。答案值唯一,不要求返回重复位置或出现次数。必须把输入数组视为只读,不能通过排序、取负标记或交换元素来改变其内容;同时只允许使用常数级额外空间。题目的进阶要求整体运行时间不超过 O(n)。

自建示例

重复值出现两次:

输入:nums = [2, 5, 1, 4, 3, 5]
输出:5
解释:数组长度为 6,因此 n = 5,所有值都在 1..5 中;只有 5 重复出现。

同一个值出现多次:

输入:nums = [3, 1, 3, 4, 2, 3]
输出:3
解释:3 出现三次,其他出现过的值都没有重复;题目仍只要求返回重复值 3。

把数组看成函数图

把下标 i 的下一节点定义为 nums[i]。由于每个值都在 1..n, 从下标 0 出发后会进入有限节点集合;数组长度为 n+1 而可取值只有 n 个, 重复值使这条函数链出现环。环的入口正是重复值:不同的前驱路径最终在该值汇合, 而从入口继续跟随 nums 会循环。

用 Floyd 快慢指针找环入口:先让 slow 每次走一步、fast 每次走两步, 在环内相遇;再把 slow 放回起点,两个指针都每次走一步,它们再次相遇的位置就是环入口。 全过程只读取数组,不需要修改元素或保存访问集合。

正确性说明

有限函数图中,快慢指针进入环后相对距离每轮改变一个固定步长,必然相遇。设起点到环入口距离为 mu, 相遇点到入口的环内距离为 d;相遇关系说明 mu+d 是环长的整数倍,所以把一个指针移回起点后, 两指针分别走 mu 步会同时到达入口。入口对应的值就是唯一重复的数字,故返回正确。

C++ 实现

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

代码分析

快慢阶段和入口阶段各自为 O(n),总时间复杂度为 O(n);只保存两个下标,额外空间为 O(1)。 算法依赖的是值域和长度形成的函数图,不依赖重复值只出现两次,因此也适用于题目允许的多次重复。