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

存在重复元素模块-三道题

文章目录

  • 存在重复元素
    • 217. 存在重复元素
    • 219. 存在重复元素 II
    • 220. 存在重复元素 III (SortedList+二分)
  • 小结

存在重复元素

217. 存在重复元素

题目链接:217. 存在重复元素
题目大意:给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。

注意:(1)1 <= nums.length <= 10510^5105;(2)−109-10^9109 <= nums[i] <= 10910^9109

示例:

输入:nums = [1,2,3,1]
输出:true输入:nums = [1,2,3,4]
输出:false输入:nums = [1,1,1,3,3,4,3,2,4,2]
输出:true

参考代码:

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:# 取巧return len(set(nums)) != len(nums)'''# hash maphash_map = dict()for num in nums:if num not in hash_map:hash_map[num] = 1else:return Truereturn False''''''# 计数器counter = collections.Counter(nums)for num in nums:if counter[num] > 1:return Truereturn False'''
  • (1)取巧办法:
  • 时间复杂度:O(1)O(1)O(1)
  • 空间复杂度:O(n)O(n)O(n),其中 nnnnumsnumsnums 的长度。
  • (2)hash map办法:
  • 时间复杂度:O(n)O(n)O(n)
  • 空间复杂度:O(n)O(n)O(n)
  • (3)计数器办法:
  • 时间复杂度:O(n)O(n)O(n)
  • 空间复杂度:O(n)O(n)O(n)

219. 存在重复元素 II

题目链接:219. 存在重复元素 II
题目大意:给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。

注意:(1)1 <= nums.length <= 10510^5105;(2)−109-10^9109 <= nums[i] <= 10910^9109;(3)0 <= k <= 10510^5105

示例:

输入:nums = [1,2,3,1], k = 3
输出:true输入:nums = [1,0,1,1], k = 1
输出:true输入:nums = [1,2,3,1,2,3], k = 2
输出:false

参考代码:

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:hash_map = dict()for i,num in enumerate(nums):if num not in hash_map:hash_map[num] = ielse:if i - hash_map[num] <= k:return Truehash_map[num] = ireturn False
  • 时间复杂度:O(n)O(n)O(n),其中 nnnnumsnumsnums 的长度。
  • 空间复杂度:O(n)O(n)O(n)

220. 存在重复元素 III (SortedList+二分)

题目链接:220. 存在重复元素 III
题目大意:给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。
如果存在则返回 true,不存在返回 false。

注意:(1)0 <= nums.length <= 2∗1042 * 10^42104;(2)−231-2^{31}231 <= nums[i] <= 231−12^{31} - 12311;(3)0 <= k <= 10410^4104;(4)0 <= t <= 231−12^{31} - 12311

示例:

输入:nums = [1,2,3,1], k = 3, t = 0
输出:true输入:nums = [1,0,1,1], k = 1, t = 2
输出:true输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false

参考代码:

from sortedcontainers import SortedList class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:wd  = SortedList()n = len(nums)for i in range(n):# print(wd)if i>k:wd.remove(nums[i-1-k])wd.add(nums[i])idx = bisect.bisect_left(wd,nums[i])if idx>0 and abs(wd[idx]-wd[idx-1])<=t:return Trueif idx<len(wd)-1 and abs(wd[idx+1]-wd[idx])<=t:return Truereturn False
  • 时间复杂度:O(nlog⁡k)O(n \log{k})O(nlogk),其中 nnn为数组的长度,TreeSet 基于红黑树,查找和插入都是 O(log⁡k)O(\log{k})O(logk) 复杂度。
  • 空间复杂度:O(k)O(k)O(k)

小结

  • 这三道题挺有趣的,之间的关联并不是非常大,不过都用到了哈希表这个容器,是一套不错的练习题,总结记录一下,便于快速查询,加油(23.3.3)。

相关文章:

存在重复元素模块-三道题

文章目录存在重复元素217. 存在重复元素219. 存在重复元素 II220. 存在重复元素 III &#xff08;SortedList二分&#xff09;小结存在重复元素 217. 存在重复元素 题目链接&#xff1a;217. 存在重复元素 题目大意&#xff1a;给你一个整数数组 nums 。如果任一值在数组中出…...

3种方法删除7-Zip压缩包的密码

7-Zip压缩软件是一款完全免费且开源的软件&#xff0c;不仅能压缩和解压7-Zip压缩包&#xff0c;还能给压缩包设置打开密码。 有些小伙伴可能会遇到这样的问题&#xff0c;7-Zip压缩包设置密码后&#xff0c;过了一段时间不需要密码保护了&#xff0c;或者一不小心忘记了密码&…...

Codeforces Round 855 (Div. 3)(A~F)

A. Is It a Cat?定义满足条件的字符串为&#xff1a;其中仅可能含有meow四种字母的大小写&#xff0c;而且相同种类的字母必须挨在一起&#xff0c;四种字母的顺序必须按照meow排列。给出一个字母串&#xff0c;求是否满足条件。思路&#xff1a;感觉是个很麻烦的模拟。首先把…...

【SpringCloud】SpringCloud详解之Feign实战

目录前言SpringCloud Feign远程服务调用一.需求二.两个服务的yml配置和访问路径三.使用RestTemplate远程调用(order服务内编写)四.使用Feign远程调用(order服务内配置)五.自定义Feign配置(order服务内配置)六.Feign配置日志(oder服务内配置)七.Feign调优(order服务内配置)八.抽…...

tuts4you上lena‘s40个crackme(1)

本来是不打算写文章了&#xff0c;因为懒&#xff0c;想以后通过录屏的形式保存一下自己学的路程。但奈何开学后一直没找到机会&#xff0c;在宿舍也不愿意大吼大叫的讲东西&#xff0c;只好再写写文章了 最近学了一些汇编语言和逆向工程&#xff0c;所以就想通过这40给题目来看…...

研讨会回顾 | Perforce版本控制工具Helix Core入华十年,携手龙智赋能企业大规模研发

2023年2月28日&#xff0c;龙智联合全球领先的数字资产管理工具厂商Perforce共同举办Perforce on Tour网络研讨会&#xff0c;主题为“赋能‘大’研发&#xff0c;助力‘快’交付”。 作为Perforce Helix Core产品在中国地区的唯一授权合作伙伴&#xff0c;龙智董事长何明女士为…...

C++ vscode 开发环境搭建

C vscode 开发环境搭建 笔记内容&#xff1a; C vscode 开发环境搭建准备了解g命令编译调试掌握使用launch.json和tasks.json配置文件编译调试了解使用cmake构建 git: https://github.com/weichangk/hellocpp/tree/master/vscodecmakecpp 环境搭建准备 安装vscode安装qt&a…...

ANR系列(二)——ANR监听方案之SyncBarrier

前言 在项目中经常遇到了手机假死问题&#xff0c;无规律的偶现问题&#xff0c;大量频繁随机操作后&#xff0c;便会出现假死&#xff0c;整个应用无法操作&#xff0c;不会响应事件&#xff0c;会发生各种奇怪的ANR&#xff0c;且trace不固定。而SyncBarrier是其中的罪魁祸首…...

【完美解决】应用程序无法正常启动(0xc000007b)请单击“确定”关闭应用程序

年期安装CorelDRAW X8 (64-Bit)&#xff0c;安装完成之后运行一点毛病都没有&#xff0c;可是过了两三个月&#xff0c;再打开就出现“应用程序无法正常启动(0xc000007b)请单击“确定”关闭应用程序”这个提示框&#xff0c;如下图示 出现这个问题我就上网查找&#xff0c;无非…...

.NET基础加强第二课--静态成员,静态类

类 实例类 默认是实例类 静态类 在类前加上static ,就是静态类 静态类中&#xff0c;所有包含的成员必须是静态成员 实例成员是属于具体某个对象的 举例代码 Person p1 new Person(); p1.Age 20; p1.Name “张三”; class Person { public string Name { get; set;…...

【UML+OOPC嵌入式C语言开发】使用C语言实现一个面向对象语言才能够实现的类

文章目录简述OOPC开发环境知识讲解函数示例类的实现示例接口实现示例&#xff08;前面两部分有点无聊&#xff0c;如果大家没兴趣看可以直接从知识讲解开始看&#xff09; 简述OOPC oopc&#xff0c;是一种轻量级的面向对象的C语言编程框架&#xff0c; LW_OOPC是Light-Weight …...

软件测试自动化Java篇【Selenium+Junit 5】

文章目录Selenium环境部署自动化测试例子常见的元素操作窗口等待浏览器的操作弹窗选择器执行脚本文件上传浏览器参数Junit 5导入依赖Junit 4 和 Junit5 注解对比断言测试顺序参数化单参数多参数动态参数测试套件指定类来运行测试用例指定包名来运行包下测试用例Selenium 为什么…...

Clip:学习笔记

Clip 文章目录Clip前言一、原理1.1 摘要1.2 引言1.3 方法1.4 实验1.4.1 zero-shot Transfer1.4.2 PROMPT ENGINEERING AND ENSEMBLING1.5 局限性二、总结前言 阅读论文&#xff1a; Learning Transferable Visual Models From Natural Language Supervision CLIP 论文逐段精读…...

STM32CubexMX与FreeRTOS学习

目录 LED与EXTI配置 基本定时器使用 软件定时器 在HAL库中实现printf 重点--记得自己添加头文件 队列实现 二值信号量实现 计数信号量实现 DMA实现 ADC配置 RTC配置 看门狗 窗口看门狗 FreeRTOS结合MX软件开发&#xff0c;基础配置直接生成&#xff0c;我们只…...

Master Slave 主从同步错误 Slave_IO_Running:NO/Slave_SQL_Running: No

Master Slave 主从同步错误 Slave_IO_Running:NO Slave_SQL_Running:Yes #在Slave库上查看状态 mysql> show slave status\G Slave_IO_Running: No Slave_SQL_Running: Yes #重启master库&#xff1a;service mysqld restart mysql> show master status; ------------…...

JavaScript函数之prototype原型和原型链

文章目录1. 原型2. 显式和隐式原型3. 原型链3.1 访问顺序4. instanceof4.1 如何判断1. 原型 函数的prototype属性 每个函数都有一个prototype属性&#xff0c;它默认指向一个Object空对象&#xff08;即&#xff1a;原型对象&#xff09;。原型对象中有一个属性constructor&a…...

从上海分时电价机制调整看转供电用户电能计费

安科瑞 耿敏花2022年12月16日&#xff0c;上海市发改委发布《关于进一步完善我市分时电价机制有关事项的通知》(沪发改价管〔2022〕50号)。通知明确上海分时电价机制&#xff0c;一般工商业及其他两部制、大工业两部制用电夏季&#xff08;7、8、9月&#xff09;和冬季&#xf…...

TypeScript类型体操:获取数组中元素对象属性的值作为新类型

title: TypeScript类型体操&#xff1a;获取数组中元素对象属性的值作为新类型 date: 2023-03-03 20:58:24 categories: TypeScript类型体操 tags: TypeScript类型体操TypeScript 首先先说获取数组中元素对象属性的值作为新类型的解决方案 使用 as const 强调不可变数组使用 …...

npm,yarn和pnpm

npm扁平的node_modules结构比如项目依赖了A 和 C&#xff0c;而 A 和 C 依赖了不同版本的 B1.0 和 B2.0&#xff0c;D也依赖B1.0, node_modules 结构如下&#xff1a;node_modules ├── A1.0.0 ├── B1.0.0 └── C1.0.0└── node_modules└── B2.0.0C依赖的B2.0因为版…...

【算法】【数组与矩阵模块】在排好序的矩阵中找数,时间复杂度O(M+N)

目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过&#xff0c;但是不保证100%的测试用例&#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识&#xff01; 问题介绍 …...

如何高效使用Windows键盘记录工具:开源监控解决方案

如何高效使用Windows键盘记录工具&#xff1a;开源监控解决方案 【免费下载链接】keylogger Keylogger for Windows. 项目地址: https://gitcode.com/gh_mirrors/keylogg/keylogger Windows键盘记录工具Keylogger for Windows是一款专为系统管理员和安全研究人员设计的开…...

1k Star的p-retry,让异步操作失败自动重试

文章目录1k Star的p-retry&#xff0c;让异步操作失败自动重试核心功能适用场景注意事项1k Star的p-retry&#xff0c;让异步操作失败自动重试 sindresorhus开源的p-retry项目&#xff0c;目前在GitHub上获得1009个Star。这个库的核心功能是为异步操作添加重试机制&#xff0c…...

选择Token Plan套餐后在实际开发中感受到的成本控制优势

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 选择Token Plan套餐后在实际开发中感受到的成本控制优势 1. 从按量计费到固定额度的转变 在项目开发的早期阶段&#xff0c;尤其是…...

OpenMMLab MMTracking 目标跟踪算法库

MMTracking是OpenMMLab&#xff08;商汤科技与港中文MMLab联合推出&#xff09;体系下的一款开源视频目标感知工具箱。你可以把它理解为“视频版”的MMDetection&#xff0c;它将该领域内纷繁复杂的算法、数据集和评估标准&#xff0c;统一整合到了一个高效、模块化的框架中。 …...

3大技术创新:重新定义Windows Android生态的工具体验

3大技术创新&#xff1a;重新定义Windows Android生态的工具体验 【免费下载链接】wsa-toolbox A Windows 11 application to easily install and use the Windows Subsystem For Android™ package on your computer. 项目地址: https://gitcode.com/gh_mirrors/ws/wsa-tool…...

Pinecone示例库实战指南:从向量数据库原理到RAG应用开发

1. 项目概述&#xff1a;Pinecone示例库的深度探索 如果你正在寻找一个能让你快速上手向量数据库和现代AI应用开发的“实战训练营”&#xff0c;那么Pinecone官方的 pinecone-io/examples 仓库绝对是一个不容错过的宝藏。这个仓库远不止是一个简单的代码合集&#xff0c;它更…...

React Native跨平台AI聊天应用开发实战:架构设计与性能优化

1. 项目概述&#xff1a;一个全功能的跨平台AI聊天伴侣如果你和我一样&#xff0c;既是移动端开发者&#xff0c;又是AI应用的深度用户&#xff0c;那么你肯定经历过这样的困境&#xff1a;想在手机上随时随地、流畅地和ChatGPT对话&#xff0c;却发现官方App要么功能受限&…...

AI产品经理转型指南——传统PM如何不被淘汰

文章针对想转型AI产品经理但缺乏经验的人提供了实用的转型路径。首先&#xff0c;文章指出传统产品经理的焦虑源于视角受限&#xff0c;而非技术能力不足&#xff0c;并提出AI无法替代产品经理对用户、业务和组织的深度理解。接着&#xff0c;文章建议转型者从“用AI重做一遍”…...

AI 驱动单元测试生成:智能优先级与自动化验证实践

1. 项目概述如果你和我一样&#xff0c;长期在维护一个中大型的 TypeScript 项目&#xff0c;那么“补单元测试”这件事&#xff0c;大概率是你技术债清单上那个永远在滚动、却很少被真正划掉的任务。手动写测试枯燥耗时&#xff0c;尤其是面对那些遗留的、逻辑复杂的业务函数时…...

Unity游戏任务系统框架解析:数据驱动与事件架构实战

1. 项目概述&#xff1a;一个为游戏开发者准备的灵活任务系统如果你正在开发一款RPG、开放世界或者任何需要任务驱动的游戏&#xff0c;那么“任务系统”绝对是你绕不开的核心模块。最近我在GitHub上发现了一个名为shomykohai/quest-system的开源项目&#xff0c;它不是一个完整…...