LeetCode287——寻找重复数

本是古典何须时尚 2022-01-25 22:13 250阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/find-the-duplicate-number/comments/][https_leetcode-cn.com_problems_find-the-duplicate-number_comments]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：链表

### 思路：[LeetCode142——环形链表II][LeetCode142_II]的抽象 ###

本题难在条件限制太多。

（1）不能更改原数组——禁止我们排序。

（2）只能使用O(1)的空间——禁止我们用哈希表记录每个数字出现次数。

（3）时间复杂度小于O(n ^ 2)——禁止我们使用暴力破解法。

（4）数组中只有一个重复的数字，但它可能不止重复出现一次——禁止我们使用求和的方法。

本质上，本题是[LeetCode142——环形链表II][LeetCode142_II]的抽象，我们如何去构建这么一个环形链表呢？以题目所给的示例1——\[1, 3, 4, 2, 2\]为例，我们的环形链表构造如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1][]

上述环形链表是如何构造出来的呢？

（1）以索引为0处的1为例，其值是1，因此第一个点是1。

（2）索引为1处的值是3，因此第二个点是3。

（3）索引为3处的值是2，因此第三个点是2。

（4）索引为2处的值是4，因此第四个点是4。

（5）索引为4处的值是2，因此4指向2形成环。

**2是环的入口，也是所要求的重复数字**。

抽象出了这么一个环形链表后，我们的问题就变成了如何求环形链表中环的入口节点，这就是[LeetCode142——环形链表II][LeetCode142_II]所解决的问题。

时间复杂度是O(n)。空间复杂度是O(1)。

JAVA代码：

public class Solution {
        public int findDuplicate(int[] nums) {
            int fast = 0, slow = 0;
            while (true) {
                fast = nums[nums[fast]];
                slow = nums[slow];
                if (fast == slow) {
                    fast = 0;
                    while (nums[slow] != nums[fast]) {
                        fast = nums[fast];
                        slow = nums[slow];
                    }
                    return nums[slow];
                }
            }
        }
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_find-the-duplicate-number_comments]: https://leetcode-cn.com/problems/find-the-duplicate-number/comments/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220126/19a20fccbaba4b35b6387fdf8ec66ec2.png
[LeetCode142_II]: https://blog.csdn.net/qq_41231926/article/details/86105434
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1]: /images/20220126/0a8492ae2a1f4021ae8e447565590cef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2]: /images/20220126/aa8e4128f645421db03caaa4530a46f3.png