当前位置: 首页 > news >正文

14. 不修改数组找出重复的数字

文章目录

  • Question
  • Ideas
  • Code

Question

给定一个长度为 n+1
的数组nums,数组中所有的数均在 1∼n的范围内,其中 n≥1。

请找出数组中任意一个重复的数,但不能修改输入的数组。

数据范围
1≤n≤1000

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。
思考题:如果只能使用 O(1)的额外空间,该怎么做呢?

Ideas

  • 哈希表,遍历整个数组,判断是否有元素在哈希表中,如果在,该元素就是重复元素,否则加入哈希表。时间复杂度O(n),空间复杂度O(n)
  • 利用题目性质,由于题目中的数组长度为n+1,数组元素的范围是[1, n],那么必然有一个数字是重复的。(抽屉原理:有n+1个苹果,放在n个抽屉里,那么至少有一个抽屉里面有2个苹果。对应到本题就是有n+1个数字,每个数字的范围是[1,n],那么至少有一个数字出现了两次)。接着我们可以考虑如何利用这个性质。从区间角度出发,我们将整个数组划分为左右区间,如果重复的数字在左区间,那么左区间元素的个数一定>左区间的长度,右区间同理。这样问题可以依据是否存在重复元素划分,就有了两段性,就可以利用二分。注意,这里我们二分的是数值的范围[1,n],而不是区间的长度,因为我们要找的是重复的数字。具体做法为:将区间划分为两个子区间[l,mid], [mid+1, r]计算任意一个区间的元素的个数cnt,与当前区间的长度进行对比,如果cnt>区间长度,那么该区间存在重复元素,否则另外一个区间存在重复元素。最终返回的是数值范围l,而不是nums[l]。时间复杂度O(logn),空间复杂度O(1)

Code

class Solution(object):def duplicateInArray(self, nums):""":type nums: List[int]:rtype int"""# 哈希表 时间复杂度O(n), 空间复杂度O(n)# s = set()# for i in nums:#     if i in s:#         return i#     s.add(i)# 抽屉原理:n+1个苹果放在n个盒子中,那么至少存在一个盒子有两个苹果# 将数值范围区间划分为两份,分别统计每个区间元素个数 # 如果区间元素个数>区间长度,说明重复的元素在该区间,否则就是另外一个区间# 时间复杂度O(nlogn), 空间复杂度O(1)n = len(nums) - 1l, r = 1, nwhile l < r: # [l, mid], [mid+1, r]mid = l + r >> 1# 统计[l, mid]区间中的元素个数 这里任意统计一个区间元素个数即可cnt = 0for i in nums:if i >= l and i <= mid:cnt += 1# 说明在左区间if mid - l + 1 < cnt:r = midelse:l = mid + 1return l

http://www.mrgr.cn/news/62899.html

相关文章:

  • 【Nas】X-DOC:在Mac OS X 中使用 WOL 命令唤醒局域网内 PVE 主机
  • 从此告别文献混乱:Zotero必装的40个插件
  • B站狂神说+mybatis+如何创建一个最简单的mybatis程序
  • 时序分解 | TTNRBO-VMD改进牛顿-拉夫逊算法优化变分模态分解
  • JVM1.8内存模型
  • Android OpenGL ES详解——裁剪Scissor
  • 【论文速读】Optimization-based Prompt Injection Attack to LLM-as-a-Judge
  • Python 从入门到实战43(Pandas数据结构)
  • 哈希函数简介
  • 【调试记录】CARLA车辆actor设置BehaviorAgent自动规划后不沿道路行驶
  • Terraform Provider 加速方案
  • 什么是 Spring Cloud Bus?我们需要它吗?
  • 【AI日记】24.10.31 学习LangChain和寻找AI研究报告(比如麦肯锡)
  • ROS(快速初步入门)
  • 谷歌Google搜索广告账户代理开户!
  • iDP3复现代码运行逻辑全流程(一)——部署全流程代码逻辑梳理(Learning)
  • python opencv1
  • 金蝶云苍穹的Extension与Nop平台的Delta的区别
  • 基于LORA的一主多从监测系统_4G模块上巴法云
  • Linux高阶——1027—进程间关系相关
  • SpringFactoriesLoader
  • Java项目实战II基于Java+Spring Boot+MySQL的编程训练系统(源码+数据库+文档)
  • VB中如何处理国际化(Internationalization)和本地化(Localization)
  • 低代码的崛起:改变开发的游戏规则
  • Leetcode 移除元素
  • vector中去除重复的元素