【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)

这篇具有很好参考价值的文章主要介绍了【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在最前面

刷一道力扣热题100吧
难度中等

https://leetcode.cn/problems/find-the-duplicate-number/?envType=study-plan-v2&envId=top-100-liked

一年半前做过这题,但是时间复杂度不够。现在重新学一下
主要是用到了弗洛伊德的乌龟和兔子方法

算法预览:

  1. 初始化:从两个指针开始,“乌龟"和"兔子”,都指向第一个元素。

  2. 第一阶段 - 检测循环:每次移动乌龟一步(tortoise = nums[tortoise]),兔子两步(hare = nums[nums[hare]])。继续这个过程,直到他们在循环中相遇。

  3. 第二阶段 - 找到循环的入口:将乌龟重置到数组的开头。将乌龟和兔子都每次移动一步。他们再次相遇的地方就是循环的入口,对应着重复的数字。

【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法),蓝桥杯python,leetcode,算法,职场和发展,学习,程序人生,AI编程,python

理解解决 “寻找重复数” 问题的算法

在处理 “287. 寻找重复数” 这个问题时,我们面临一个独特的挑战:在不修改数组并且只使用常数额外空间的情况下找出数组中的一个重复数字。

这种情况使得传统的方法,如排序或哈希表变得不可行。

然而,有一种巧妙的方法可以解决这个问题,这就是著名的弗洛伊德的乌龟和兔子算法,一种用于检测循环的方法。

问题描述

给定一个包含 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

提示:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

进阶:

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

弗洛伊德的乌龟和兔子方法

这个算法主要用于检测值序列中的循环。以下是我们适应我们问题的方式:

  1. 初始化:从两个指针开始,“乌龟"和"兔子”,都指向第一个元素。

  2. 第一阶段 - 检测循环:每次移动乌龟一步(tortoise = nums[tortoise]),兔子两步(hare = nums[nums[hare]])。继续这个过程,直到他们在循环中相遇。

  3. 第二阶段 - 找到循环的入口:将乌龟重置到数组的开头。将乌龟和兔子都每次移动一步。他们再次相遇的地方就是循环的入口,对应着重复的数字。

为什么这个方法有效?

关键的洞见是将数组视为一个链表,其中每个元素指向下一个元素的位置。例如,在一个数组 [2, 5, 1, 1] 中,2 指向位置 25 指向位置 1,形成了一个循环。由于存在重复,因此一定存在一个循环。该算法有效地找到了这个循环及其入口。

代码

from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 初始化乌龟和兔子指针
        tortoise = hare = nums[0]

        # 第一阶段:使用快慢指针找到循环
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break

        # 第二阶段:找到循环的入口
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]

        return hare

# 示例使用
sol = Solution()
print(sol.findDuplicate([1,3,4,2,2]))  # 输出应为 2
print(sol.findDuplicate([3,1,3,4,2]))  # 输出应为 3

复杂度

这种方法的美妙之处在于其效率:

  • 时间复杂度:O(n)。算法的两个阶段都在线性时间内运行。
  • 空间复杂度:O(1)。只使用了两个额外变量(乌龟和兔子)。

总结回顾

弗洛伊德的乌龟和兔子算法是解决涉及序列中循环的问题的一个巧妙的解决方案。它在寻找数组中的重复数字的应用是一个典型的例子,展示了如何跳出常规思维框架,将算法适应于独特问题。这个解决方案不仅满足了常数空间和不修改数组的约束,而且做到了高效。文章来源地址https://www.toymoban.com/news/detail-754590.html

到了这里,关于【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】287.寻找重复数

    给定一个包含  n + 1  个整数的数组  nums  ,其数字都在  [1, n]  范围内(包括  1  和  n ),可知至少存在一个重复的整数。 假设  nums  只有  一个重复的整数  ,返回  这个重复的数  。 你设计的解决方案必须  不修改  数组  nums  且只用常量级  O(1)  的额外空间。

    2024年02月14日
    浏览(32)
  • 【LeetCode】287. 寻找重复数

    思路 要解决这道题首先要理解如何将输入的数组看作为链表。对于数组 nums 中的数字范围在 [1, n],考虑两种情况: 如果数组中没有重复的数字,以 [1, 3, 4, 2] 为例,将数组下标 n 和 nums[n] 建立映射关系f(n),即 n-f(n): 0-1, 1-3, 2-4, 3-2 ,从下标 0 出发, 根据 f(n) 计算出一个值,

    2024年02月14日
    浏览(36)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(43)
  • 弗洛伊德循环查找算法-原理

    本文灵感来自哔哩哔哩视频  视频链接: 弗洛伊德循环查找算法 算法代码(java) 弗洛伊德循环查找算法中第二次相遇的地方就是循环的起始点,这个性质的证明是基于数学的原理。这是因为在第一次相遇时,慢指针 `slow` 和快指针 `fast` 已经处于同一个循环内。设链表起点到环

    2024年01月19日
    浏览(46)
  • 最短路径——弗洛伊德算法

    对于这类最短路径问题,DIF算法也可以解决,只需要 定义一个二维数组 ,以 数组的横坐标作为有向网顶点的下标 , 循环n次 依次求解各个源点到其余顶点的最短路径, 时间复杂度为O(n^3) 。 由于弗洛伊德算法求解该问题的的时间复杂度同为O(n^3),而且 思路简单及代码实现

    2024年01月23日
    浏览(44)
  • 40.弗洛伊德(Floyd)算法

    我们此前拆解过迪杰斯特拉(Dijkstra)算法,与它一样,弗洛伊德(Floyd)算法也是用于寻找给定的加权图中顶点间最短路径的算法。该算法是1978年图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德 及其团队发现的,以主要创始人 弗洛伊德 命名。 迪杰斯特拉算

    2024年02月06日
    浏览(36)
  • Floyd - Warshall (弗洛伊德算法)

    图中任意两点之间的最短路径问题 Dijkstra和Bellman-Ford也可以以所有点为源点,求出任意两点之间的最短距离,但是Dijstra不能解决带负权的的边,Bellman-Ford 效率慢点 Floyd算法考虑的是一条最短路径的中间节点,即简单路径p={v1 , v2,  ...  ,vn}上除v1和vn的任意节点 设K是p的一个

    2024年02月06日
    浏览(40)
  • 弗洛伊德算法(求最短路径)

    在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。 弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。 弗洛

    2024年02月06日
    浏览(46)
  • 今天学习了弗洛伊德算法(floyed)

    我自己写的模板 嘿嘿 Dijkstra算法SPFA算法但是我知道还有这些,但是今天是周末哎,我有点不想学了,我今天学的是比较差劲的一个算法(但是它好像比较好记啊),改天再学其他比较好一点的算法加强自己 输入 输出 后言:提醒自己加权值是分题目来不同权值,不是像示例

    2024年02月11日
    浏览(36)
  • 《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数

    本期给大家带来的是是《 LeetCode 热题 HOT 100 》第四题—— 寻找两个正序数组的中位数的 题目讲解 !!!() 本文目录 💥题意分析 💥解题思路: 1、直接法  (❌) 2、归并思想 (❌) ①《LeetCode》第88题——合并两个有序数组 3、二分查找(✔️) 整体思想: 题目如下

    2023年04月27日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包