Medium

题目描述

给定一个包含 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 <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次，其余整数均只出现 一次

进阶：

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

解题思路

这道题有多种解法，关键在于不能修改数组且空间复杂度要求为 O(1)。

方法一：快慢指针（推荐）

将数组看作一个链表，每个位置的值指向下一个位置。由于存在重复数字，必然会形成环。我们可以用 Floyd 判圈算法（龟兔赛跑）来找到环的入口，这个入口就是重复的数字。

算法步骤：

  1. 第一阶段：快慢指针找到相遇点
  2. 第二阶段：一个指针从起点出发，另一个从相遇点出发，以相同速度移动直到相遇

方法二：二分查找

利用鸽巢原理，统计小于等于某个数的元素个数。如果个数大于这个数，说明重复数在左半部分，否则在右半部分。

方法三：位运算

利用异或运算的性质，但实现较复杂。

快慢指针法最优雅且时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        
        // 第一阶段：找到快慢指针相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // 第二阶段：找到环的入口（重复数字）
        int ptr1 = 0, ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        
        return ptr1;
    }
};

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
        
        # 第二阶段：找到环的入口（重复数字）
        ptr1, ptr2 = 0, slow
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
        
        return ptr1

public class Solution {
    public int FindDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        
        // 第一阶段：找到快慢指针相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // 第二阶段：找到环的入口（重复数字）
        int ptr1 = 0, ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        
        return ptr1;
    }
}

var findDuplicate = function(nums) {
    let slow = 0, fast = 0;
    
    // 第一阶段：找到快慢指针相遇点
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // 第二阶段：找到环的入口（重复数字）
    let ptr1 = 0, ptr2 = slow;
    while (ptr1 !== ptr2) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    
    return ptr1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
快慢指针O(n)O(1)
二分查找O(n log n)O(1)
位运算O(n log n)O(1)

相关题目