当前位置：首页 > article >正文

LeetCode题练习与总结：寻找重复数--287

article 2024/10/8 16:11:46

一、题目描述

给定一个包含 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 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

二、解题思路

由于数组中的数字都在 [1, n] 范围内，我们可以使用快慢指针的方法来解决这个问题。这个方法类似于在链表中寻找环的入口。具体步骤如下：

将数组视为一个链表，其中每个元素的值表示下一个元素的索引（即 nums[nums[i]] 是下一个元素的索引）。
定义快慢指针，分别初始化为 nums[0] 和 nums[nums[0]]。
快指针每次移动两步，慢指针每次移动一步。
当快慢指针相遇时，将慢指针重新指向数组起始位置，并让快慢指针每次都移动一步。
当快慢指针再次相遇时，相遇的元素即为重复的数。

三、具体代码

class Solution {
    public int findDuplicate(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;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

第一个 while 循环：在这个循环中，快指针每次移动两步，慢指针每次移动一步。由于数组中存在一个环，快指针最终一定会追上慢指针。假设环的长度为 L，那么快指针最多移动 2L 步，慢指针最多移动 L 步。由于每个元素最多被访问两次（一次由快指针，一次由慢指针），所以这个循环的时间复杂度是 O(n)。
第二个 while 循环：在这个循环中，快慢指针每次都移动一步。它们从数组的开始和环的入口同时移动，最终在环的入口相遇。这个循环中，每个元素最多被访问一次，所以这个循环的时间复杂度也是 O(n)。

由于这两个循环是顺序执行的，总的时间复杂度是 O(n) + O(n) = O(n)。

2. 空间复杂度

在这个算法中，我们只使用了几个额外的变量（slow 和 fast），这些变量只占用常数级的额外空间，因此空间复杂度是 O(1)。我们不需要额外的数据结构来存储中间结果或索引，所以空间效率非常高。

五、总结知识点

数组与索引关系：数组中的每个元素都可以被视为指向下一个元素的索引，这种关系可以用来模拟链表的行为。
快慢指针技术：快慢指针是一种用于解决链表中的环问题的算法技术。在这个问题中，尽管输入是一个数组，但是通过将数组元素视为链表节点，我们能够应用快慢指针技术来找到重复的元素。
循环与相遇点：使用 while 循环来迭代数组，直到快慢指针相遇，这表明它们在环中相遇了。
链表环的入口：当快慢指针相遇后，将一个指针重新指向数组的起始位置，然后两个指针以相同的速度移动，它们会在环的入口（即重复的元素）相遇。
数组边界条件：算法假设输入数组至少包含一个重复元素，并且数组的长度至少为 2。
整型变量操作：代码中涉及基本的整型变量赋值和比较操作，这是 Java 程序设计的基础。
递归与迭代：虽然代码没有直接使用递归，但是快慢指针的移动可以看作是一种迭代过程，它隐式地模拟了递归访问链表节点。