美文网首页
287. 寻找重复数

287. 寻找重复数

作者: 追风骚年 | 来源:发表于2021-02-25 19:44 被阅读0次

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,找出 这个重复的数 。

题目言简意赅,但是这道题被划分为双指针模块,想想可能没那么容易。
试了意向解法都可以通过:

  • 先排序,一遍 for 循环
  • 使用 map 做一下缓存
  • 测试两层 for 循环也可以通过
  • 快慢指针!

既然要使用快慢指针,那必须得构造出一个链表,并且慢指针是指向下个节点,快指针是指向下下个节点,而这题恰巧是,n + 1 个整数都小于 n,那么数组的索引和值可以在里面循环使用,此次的值可以作为下一次的索引。并且有个烧脑的事情是,在快慢指针第一次相遇的时候并不一定是重复的整数,而环的入口点则恰好是重复的整数,labuladong 的算法上提到一个环入口的计算方法,终于也排上了用场。

func findDuplicate(nums []int) int {
    fast, slow := 0, 0 // 索引

    slow = nums[slow]       // 指向下一个
    fast = nums[nums[fast]] // 指向下下个

    for slow != fast { // 一直到相遇
        slow = nums[slow]       // 指向下一个
        fast = nums[nums[fast]] // 指向下下个
    }

    fast = 0
    for slow != fast { // 继续前进 直到相遇就是环的入口点
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

参考文档

相关文章

  • 寻找重复数

    287. 寻找重复数[https://leetcode-cn.com/problems/find-the-dupl...

  • LeetCode 287. 寻找重复数 | Python

    287. 寻找重复数 题目来源:力扣(LeetCode)https://leetcode-cn.com/probl...

  • LeetCode 287.寻找重复数

    ?博客原文 :《LeetCode 287.寻找重复数 - JavaScript》 题目描述:给定一个包含 n +...

  • 287. 寻找重复数

    题目描述 给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知...

  • 287. 寻找重复数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一...

  • 287. 寻找重复数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一...

  • 287. 寻找重复数

    【题目描述】给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可...

  • 287. 寻找重复数

  • 287. 寻找重复数

    287. 寻找重复数 问题 给定一个包含 个整数的数组 ,其数字都在 到 之间(包括 和 ),可知至少存在...

  • 287.寻找重复数

    给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一...

网友评论

      本文标题:287. 寻找重复数

      本文链接:https://www.haomeiwen.com/subject/nrksfltx.html