[python 刷题] 287 Find the Duplicate Number

2023-10-22 07:45

本文主要是介绍[python 刷题] 287 Find the Duplicate Number,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[python 刷题] 287 Find the Duplicate Number

题目:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

快慢指针

之前其实大概说过这道题用快慢指针做,不过时隔一年,重新写的时候发现只是记得一个 快慢指针,但是不记得具体的实现方法了,所以想着重新整理一下。

这道题本质上是个链表题

首先捋一下题目的重点:

  1. 数组中包含 n + 1 个数字
  2. 每个数字的限定范围为 [1, n]
  3. 有且只有一个重复数字
  4. 不能排序数组 (❌ 排序)
  5. 不能用多余的数据结构去存储出现的数字 (❌ 哈希表)

首先考虑一下,如果数组中不包含重复数字,并且每个数字的限定范围依旧是 [1, n] 的场景,那也就是说,排序后一定会出现 [ 1 , 2 , . . . , n ] [1, 2, ..., n] [1,2,...,n],将当前下标中的值视作下个数字的下标,视觉上的效果就是这样的:

在这里插入图片描述

这个时候就算随意将其打乱,最终形成的结果也是:

在这里插入图片描述

也就是说不管怎么打乱,它都会存在一个 1-to-1 的关系,最终结束循环。但是如果数组中出现了一个重复数字,运用快慢指针的技巧,在某个情况下 (依旧是 O ( n ) O(n) O(n) 的时间复杂度),一定会两个指针一定会通过重复数字,而抵达同一个结点的情况下。

以我手残不小心打错的 LC 提供的案例来说,视觉效果如下:

在这里插入图片描述

可以非常清楚的看到,出现了两个结点(这里将 array 中的每个 index 视作一个结点)指向另外一个结点的情况。

简单的过一下这个案例,效果如下:

黄色代表慢指针,蓝色代表快指针,绿色代表两点相交

iterationgraph
1在这里插入图片描述
2在这里插入图片描述
3在这里插入图片描述
4在这里插入图片描述
5在这里插入图片描述

最终快慢指针是否会落在重复数字上与数组有关,LC 上的一个案例 [2,5,9,6,9,3,8,9,7,1] 最终的落点在 7 上。这个数组比较长,我就不跑了。

现在已经找到这个圈了,接着将其中一个指针指向数组的开始,继续走到两点相交的情况,就能够找到重复的点了:

在这里插入图片描述

我个人觉得,这个指向重复的点还是挺清楚的,开始和结束的指针都一样,也就代表着圈的开始,所以这就是重复的数字。

代码如下:

class Solution:def findDuplicate(self, nums: List[int]) -> int:slow, fast = 0, 0while True:slow = nums[slow]fast = nums[nums[fast]]if slow == fast:breakslow = 0while True:slow = nums[slow]fast = nums[fast]if slow == fast:return slow

这个算法的时间复杂度为 O ( n ) O(n) O(n),是属于 Follow up 的解法

二分搜索

这个二分搜索也属于变种方法,其思路是:

  1. 找到一个数字 k ∈ [ 1 , n − 1 ] k \in [1, n - 1] k[1,n1]

    这里取 [ 1 , n − 1 ] [1, n - 1] [1,n1] 这个范围的原因是,因为重复数字的关系,数组里面最大的数字只可能是 n − 1 n - 1 n1

  2. 计算小于等于 k k k 的数字,使得 c o u n t ( k ) = ∣ X ∣ x ∈ n u m s a n d x ≤ k ∣ count(k) = |{X | x \in nums \, and \, x \le k}| count(k)=Xxnumsandxk

1, 3, 4, 2, 2 为例,这里的 k k k 取 3,那么计算小于等于 3 的数字就有 4 个,那么自然就包含一个重复数字,反之亦然。

代码如下:

class Solution:def findDuplicate(self, nums: List[int]) -> int:l, h = 1, len(nums) - 1while l < h:m = (l + h) // 2c = sum(1 for num in nums if num <= m)if c <= m:l = m + 1else:h = mreturn l

因为这里是一个二分搜索整个数组的长度+遍历整个数组,所以时间复杂度为 O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))

这篇关于[python 刷题] 287 Find the Duplicate Number的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/260066

相关文章

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

Python中你不知道的gzip高级用法分享

《Python中你不知道的gzip高级用法分享》在当今大数据时代,数据存储和传输成本已成为每个开发者必须考虑的问题,Python内置的gzip模块提供了一种简单高效的解决方案,下面小编就来和大家详细讲... 目录前言:为什么数据压缩如此重要1. gzip 模块基础介绍2. 基本压缩与解压缩操作2.1 压缩文

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传:从崩溃边缘抢救进度二、多线程加速:榨干网络带宽三、速度控制:做网络的好邻居四、终端交互

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,:本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释?示例:三、单行注释语法:以 China编程# 开头,后面的内容为注释内容示例:示例:四