[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

相关文章

基于Python开发一个图像水印批量添加工具

《基于Python开发一个图像水印批量添加工具》在当今数字化内容爆炸式增长的时代,图像版权保护已成为创作者和企业的核心需求,本方案将详细介绍一个基于PythonPIL库的工业级图像水印解决方案,有需要... 目录一、系统架构设计1.1 整体处理流程1.2 类结构设计(扩展版本)二、核心算法深入解析2.1 自

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

Python自动化批量重命名与整理文件系统

《Python自动化批量重命名与整理文件系统》这篇文章主要为大家详细介绍了如何使用Python实现一个强大的文件批量重命名与整理工具,帮助开发者自动化这一繁琐过程,有需要的小伙伴可以了解下... 目录简介环境准备项目功能概述代码详细解析1. 导入必要的库2. 配置参数设置3. 创建日志系统4. 安全文件名处

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

Python办公自动化实战之打造智能邮件发送工具

《Python办公自动化实战之打造智能邮件发送工具》在数字化办公场景中,邮件自动化是提升工作效率的关键技能,本文将演示如何使用Python的smtplib和email库构建一个支持图文混排,多附件,多... 目录前言一、基础配置:搭建邮件发送框架1.1 邮箱服务准备1.2 核心库导入1.3 基础发送函数二、

Python包管理工具pip的升级指南

《Python包管理工具pip的升级指南》本文全面探讨Python包管理工具pip的升级策略,从基础升级方法到高级技巧,涵盖不同操作系统环境下的最佳实践,我们将深入分析pip的工作原理,介绍多种升级方... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核