当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.287.Find the Duplicate Number 数组中重复的数

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


上一篇 LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数

下一篇 LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数

阅读
评论
521
阅读预计2分钟
创建日期 2020-02-13
修改日期 2020-05-26
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论