LeetCode.287.Find the Duplicate Number 数组中重复的数

题目描述

287 Find the Duplicate Number
https://leetcode-cn.com/problems/find-the-duplicate-number/

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n^2).
There is only one duplicate number in the array, but it could be repeated more than once.

---

相似题目

Floyd判圈算法/龟兔赛跑算法

有环单链表的环长、环起点和链表长
LeetCode.141.Linked List Cycle 判断链表是否有环
LeetCode.142.Linked List Cycle II 有环链表的环起点

判圈算法的其他应用
LeetCode.287.Find the Duplicate Number 数组中重复的数
LeetCode.202.Happy Number 快乐数

---

解题过程

如果允许改变元数组的话，这道题和
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数
就完全一样了，但不允许修改。

时间复杂度 O(n)，空间复杂度 O(1) 的算法真的非常难想到，怎么想都想不到。

根据抽屉原理 n+1 个值放到 n 个下标上，肯定有 至少 2个下标对应的值一样。
把数组看做链表，即把下标 i 处的值 a[i] 看做 next 指针，也就是每个元素的值是下一个链表节点的地址，则数组转化为链表。那么一定有2个节点都指到了同一个节点。这样的问题就跟链表里是否有环一样了，有环就是两个节点指到了同一个节点。

转换为有环链表中找环起点的问题
LeetCode.142.Linked List Cycle II 有环链表的环起点

private static class SolutionV2020 {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[slow];
        // 找环交点
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        }
        // 找环入口
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_287_FindTheDuplicateNumber.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_287_FindTheDuplicateNumber.java

---