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

力扣 寻找重复数

二分,双指针,环形链表。

题目

不看完题就是排序后,用两个快慢指针移动,找到相同就返回即可。

class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int l=0;int r=1;while(r<nums.length){if(nums[l]==nums[r])return nums[r];l++; r++;}return -1;}
}

但是题要求不修改数组,因此肯定不会那么简单。先是二分查找法,由题可知,nums只有一个重复的数,且数字的大小在1到n,那么可以直接看nums[i],去遍历每个数值,然后用一个计数器去记录i,注意假设nums[x]找到了这个数,那后面的计数器nums[x+1]都是加一的,然后二分划分区间,没有重复的在左半区,重复数后的在右半区,重复数就是要找的mid。如果比目标值即重复的数小说明没有,跟目标值相等说明刚好一个,说明当前没有找到重复的数,比目标值大说明就是找到了重复数的区间,继续收缩。然后就是二分的模板了,注意比较时是比数值不是比索引。

时间复杂度: O(nlogn),空间复杂度: O(1)。

class Solution {public int findDuplicate(int[] nums) {int n = nums.length;int l = 1, r = n - 1, ans = -1;while (l <= r) {int mid = (l + r) >> 1;int cnt = 0;for (int i = 0; i < n; ++i) {if (nums[i] <= mid) {cnt++;}}if (cnt <= mid) {l = mid + 1;} else {r = mid - 1;ans = mid;}}return ans;}
}

接着是快慢指针,龟兔赛跑算法。这题由于索引跟元素值的限定范围,假如按索引指向的数值当作下一个索引,如此往复,是可以形成一个环的,即假设走到某个k+1点时指向的数值是k,然后去到索引k,索引k的数值是k+2,然后k+2的数值又是k,如此反复,这里是可以形成一个环的,而这个k+1时就是环的入口点,也是要找的重复值。然后用快慢指针,慢指针每次走一步,快指针每次走两步,相遇一次后做标记,慢指针归零,从新出发,快指针从环里出发,然后再次相遇即可找到入口点了。慢指针走一步 slow = slow.next,快指针走两步 fast = fast.next.next,换成数组就是包多一层即可。注意要排除形成自环,即索引的数值是本身,因此从零出发可以排除。

时间复杂度: O(n),空间复杂度: O(1)。

class Solution {public int findDuplicate(int[] nums) {int slow = 0, fast = 0;//初始化是相等的,所以先执行,第一次相遇找到标记点do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);//慢指针重新出发,快指针继续在环里走slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
}

 

相关文章:

力扣 寻找重复数

二分&#xff0c;双指针&#xff0c;环形链表。 题目 不看完题就是排序后&#xff0c;用两个快慢指针移动&#xff0c;找到相同就返回即可。 class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int l0;int r1;while(r<nums.length){if(nums[l]num…...

第48天:Web开发-JavaEE应用依赖项Log4j日志Shiro验证FastJson数据XStream格式

#知识点 1、安全开发-JavaEE-第三方依赖开发安全 2、安全开发-JavaEE-数据转换&FastJson&XStream 3、安全开发-JavaEE-Shiro身份验证&Log4j日志处理 一、Log4j 一个基于Java的日志记录工具&#xff0c;当前被广泛应用于业务系统开发&#xff0c;开发者可以利用该工…...

ES6笔记总结

首先我们需要了解一下什么是 ECMA&#xff1a; ECMA&#xff08;European Computer Manufacturers Association&#xff09;中文名称为欧洲计算机制造商协会&#xff0c;这 个组织的目标是评估、开发和认可电信和计算机标准。1994 年后该组织改名为 Ecma 国际 什么是 ECMAScr…...

使用Docker Desktop部署GitLab

1. 环境准备 确保Windows 10/11系统支持虚拟化技术&#xff08;需在BIOS中开启Intel VT-x/AMD-V&#xff09;内存建议≥8GB&#xff0c;存储空间≥100GB 2. 安装Docker Desktop 访问Docker官网下载安装包安装时勾选"Use WSL 2 instead of Hyper-V"&#xff08;推荐…...

经典算法 统计数字问题(常数时间解决)

统计数字问题 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排&#xff0c;每个页码都不含多余的前导数字0。例如&#xff0c;第6 页用数字6 表示&#xff0c;而不是06 或006 等。数字计数问题要求对给定书的总页码n&#xff0c;计算出书的全部页…...

基于yolov8的糖尿病视网膜病变严重程度检测系统python源码+pytorch模型+评估指标曲线+精美GUI界面

【算法介绍】 基于YOLOv8的糖尿病视网膜病变严重程度检测系统 基于YOLOv8的糖尿病视网膜病变严重程度检测系统是一款利用深度学习技术&#xff0c;专为糖尿病视网膜病变早期诊断设计的智能辅助工具。该系统采用YOLOv8目标检测模型&#xff0c;结合经过标注和处理的医学影像数…...

AcWing 5933:爬楼梯 ← 递归 / 递推 / 高精度

【题目来源】 https://www.acwing.com/problem/content/5936/ 【题目描述】 树老师爬楼梯&#xff0c;他可以每次走 1 级或者 2 级&#xff0c;输入楼梯的级数&#xff0c;求不同的走法数。 例如&#xff1a;楼梯一共有 3 级&#xff0c;他可以每次都走一级&#xff0c;或者第…...

c++ 中的容器 vector 与数组 array

当初自学 c 与 c 语言时&#xff0c;一直被指针弄的云里雾里。后来 c 中引入了容器&#xff0c;避免了指针。但是&#xff0c;一些教材把容器的章节放在书本中后面的章节&#xff0c;太不合理。应该把这种方便的功能放到前面&#xff0c;这样一些初学者就不会遇到太多生硬难懂的…...

我的世界1.20.1forge模组开发进阶物品(7)——具有动画、3D立体效果的物品

基础的物品大家都会做了对吧?包括武器的释放技能,这次来点难度,让物品的贴图呈现动画效果和扔出后显示3D立体效果,这个3D立体效果需要先学习blockbench,学习如何制作贴图。 Blockbench Blockbench是一个用于创建和编辑三维模型的免费软件,特别适用于Minecraft模型的设计…...

ubuntu22.04安装docker engine

在Ubuntu 22.04上安装Docker Engine可以通过以下步骤完成&#xff1a; 更新系统包索引&#xff1a; sudo apt update安装必要的依赖包&#xff1a; 这些包允许apt通过HTTPS使用仓库。 sudo apt install -y apt-transport-https ca-certificates curl software-properties-commo…...

性能测试测试策略制定|知名软件测评机构经验分享

随着互联网产品的普及&#xff0c;产品面对的用户量级也越来越大&#xff0c;能抗住指数级增长的瞬间访问量以及交易量是保障购物体验是否顺畅的至关重要的一环&#xff0c;而我们的性能测试恰恰也是为此而存在的。 性能测试是什么呢&#xff1f;性能测试要怎么测呢&#xff1f…...

Let‘s Encrypt免费证书的应用示例

文章目录 前言证书申请证书介绍cert.pemchain.pemfullchain.pemprivkey.pem 使用步骤搭建简易demo应用新建nginx配置文件测试SSL是否生效 总结 前言 最近在搞苹果应用上架的问题&#xff0c;据说用HTTP会被拒&#xff0c;但貌似不绝对&#xff0c;2017年苹果曾发公告说必须要求…...

threeJS——安装以及三要素

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、安装二、三要素1.场景1.1创建场景1.2向场景添加元素1.3场景属性 2.相机2.1相机特点2.2正交相机2.3空间布局2.4小姐操作 3.渲染器 总结 前言 本章简单介绍前…...

【Electron入门】进程环境和隔离

目录 一、主进程和渲染进程 1、主进程&#xff08;main&#xff09; 2、渲染进程&#xff08;renderer&#xff09; 二、预加载脚本 三、沙盒化 为单个进程禁用沙盒 全局启用沙盒 四、环境访问权限控制&#xff1a;contextIsolation和nodeIntegration 1、contextIsola…...

提示词框架介绍和使用场景

框架介绍 CO-STAR 框架 定义 CO-STAR是六个关键要素的缩写,每个字母代表一个特定的部分: Context(上下文) :提供任务的背景信息或环境 当前任务是为一家科技公司撰写一篇关于人工智能发展趋势的文章/ 需要为一场面向高中生的科普讲座准备内容Objective(目标) :明确任…...

牛客NC288803 和+和

​import java.util.Comparator;import java.util.PriorityQueue;import java.util.Scanner;​public class Main {public static void main(String[] args) {// 创建Scanner对象用于读取输入Scanner sc new Scanner(System.in);// 读取两个整数n和m&#xff0c;分别表示数组的…...

AI学习第七天

数组&#xff1a;基础概念、存储特性及力扣实战应用 在计算机科学与数学的广袤领域中&#xff0c;数组作为一种极为重要的数据结构&#xff0c;发挥着不可或缺的作用。它就像一个有序的 “数据仓库”&#xff0c;能高效地存储和管理大量数据。接下来&#xff0c;让我们深入了解…...

【uniapp原生】实时记录接口请求延迟,并生成写入文件到安卓设备

在开发实时数据监控应用时&#xff0c;记录接口请求的延迟对于性能分析和用户体验优化至关重要。本文将基于 UniApp 框架&#xff0c;介绍如何实现一个实时记录接口请求延迟的功能&#xff0c;并深入解析相关代码的实现细节。 前期准备&必要的理解 1. 功能概述 该功能的…...

XR应用测试:探索虚拟与现实的边界

引言 随着XR&#xff08;扩展现实&#xff0c;Extended Reality&#xff09;技术的快速发展&#xff0c;VR&#xff08;虚拟现实&#xff09;、AR&#xff08;增强现实&#xff09;和MR&#xff08;混合现实&#xff09;应用逐渐渗透到游戏、教育、医疗、工业等多个领域。对于…...

算法之算法思想

算法思想 ♥算法思想知识体系详解♥ | Java 全栈知识体系 经典算法思想总结 经典算法思想总结&#xff08;含LeetCode题目推荐&#xff09; | JavaGuide...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...