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

LeetCode第五天(442. 数组中重复的数据)

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

class Solution {public List<Integer> findDuplicates(int[] nums) {//思路:遍历数组,每个数-1再取模,找出真实位置,再加上数组的长度,放进数组真实的位置上//再遍历,发现数组中元素大于2倍数组长度时,将其下标+1添加进返回结果的数组int len = nums.length;for(int num : nums){//找出真实位置int x = (num - 1) % len;//加上数组长度nums[x] += len; }//创建返回结果的数组List<Integer> ret = new ArrayList<Integer>();//遍历数组,找出数组中元素大于2倍数组长度的值for(int i = 0;i < len;i++){if(nums[i] > len * 2){ret.add(i+1);}}return ret;}
}

官解:

方法一:将元素交换到对应的位置
思路与算法

由于给定的 n个数都在 [1,n]的范围内,如果有数字出现了两次,就意味着 [1,n] 中有数字没有出现过。

因此,我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0,n−1],我们需要将数 i 放在数组中下标为 i−1 的位置:

如果 i 恰好出现了一次,那么将 iii 放在数组中下标为 i−1 的位置即可;
如果 i 出现了两次,那么我们希望其中的一个 i 放在数组下标中为 i−1 的位置,另一个 i 放置在任意「不冲突」的位置 j。也就是说,数 j+1 没有在数组中出现过。
这样一来,如果我们按照上述的规则放置每一个数,那么我们只需要对数组进行一次遍历。当遍历到位置 i时,如果 nums[i]−1≠i,说明 nums[i]出现了两次(另一次出现在位置 num[i]−1),我们就可以将 num[i]\textit{num}[i]num[i] 放入答案。

放置的方法也很直观:我们对数组进行一次遍历。当遍历到位置 iii 时,我们知道 nums[i]应该被放在位置 nums[i]−1。因此我们交换 num[i]和 nums[nums[i]−1] 即可,直到待交换的两个元素相等为止。

class Solution {public List<Integer> findDuplicates(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {while (nums[i] != nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);}}List<Integer> ans = new ArrayList<Integer>();for (int i = 0; i < n; ++i) {if (nums[i] - 1 != i) {ans.add(nums[i]);}}return ans;}public void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

方法二:使用正负号作为标记
思路与算法

我们也可以给 nums[i]加上「负号」表示数 i+1已经出现过一次。具体地,我们首先对数组进行一次遍历。当遍历到位置 iii 时,我们考虑 nums[nums[i]−1]的正负性:

如果 nums[nums[i]−1] 是正数,说明 nums[i]还没有出现过,我们将 nums[nums[i]−1] 加上负号;

如果 nums[nums[i]−1]是负数,说明 nums[i]已经出现过一次,我们将 nums[i]放入答案。

细节

由于 nums[i] 本身可能已经为负数,因此在将nums[i] 作为下标或者放入答案时,需要取绝对值。

class Solution {public List<Integer> findDuplicates(int[] nums) {int n = nums.length;List<Integer> ans = new ArrayList<Integer>();for (int i = 0; i < n; ++i) {int x = Math.abs(nums[i]);if (nums[x - 1] > 0) {nums[x - 1] = -nums[x - 1];} else {ans.add(x);}}return ans;}
}

相关文章:

LeetCode第五天(442. 数组中重复的数据)

给你一个长度为 n 的整数数组 nums &#xff0c;其中 nums 的所有整数都在范围 [1, n] 内&#xff0c;且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数&#xff0c;并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问…...

chatgpt正面案例合集

现在可以用百度 百度安全验证 chatgpt用来搜索软件使用指令太牛了_个人渣记录仅为自己搜索用的博客-CSDN博客 chatgpt 使用案例 根据不同的目标群体变更文案和表达_个人渣记录仅为自己搜索用的博客-CSDN博客 倾听能力 和哪些基础能力相关 ,如何提高 chatgpt_个人渣记录仅为自…...

今日讲讲路由配置

下载安装路由 1. 下载安装路由库 npm i vue-router 2. 在 src 中新建 views 文件夹&#xff0c;在其中新建页面 3. 在 src 中新建一个 router 文件夹&#xff0c;其中新建一个 index.js import { createRouter, createWebHashHistory } from vue-router; // 导入页面 imp…...

【Rust】Shared-State Concurrency

Shared-State Concurrency channel类似于single ownership. 而shared memory类似与multiple ownership. multiple ownership是难于管理的. smarter pointer也是multiple ownership的. Rust的type system和ownership rules帮助实现正确的multiple ownership管理。 Using Mute…...

连接数据库(MySQL)的JDBC

目录 JDBC简介快速入门API详解DriverManager&#xff08;驱动管理类&#xff09;注册驱动&#xff1a;获取数据库连接(对象)&#xff1a; Connection&#xff08;数据库连接对象&#xff09;获取执行SQL的对象管理事务 Statement(执行SQL语句)执行DML、DDL语句执行DQL语句 Resu…...

golang通过参数控制HTTP server是否使用基本认证

之前写的《golang实现一个BasicAuth的HTTP server》一定会做基本认证。 本例给出了如何通过启动时候指定的参数来控制是否做基本认证 代码对比和解释 给出与上一篇中源码的diff adminhpc-1:~/go/auth_http$ diff -ruN http_rpc_server.go_bak http_rpc_server.go --- http_rp…...

javaSwing坦克大战游戏

在游戏开发领域&#xff0c;坦克大战是一款经典的游戏&#xff0c;其简单而又耐玩的玩法吸引了无数玩家。而今&#xff0c;在Java编程技术的支持下&#xff0c;我们可以用Java Swing技术轻松实现这款经典游戏。本文将介绍如何使用Java Swing技术编写坦克大战游戏&#xff0c;并…...

【面试题】数据底层原理:Elasticsearch写入流程解析

前言&#xff1a;本篇博客将介绍Elasticsearch的数据底层原理&#xff0c;涉及数据写入的过程以及相关概念。我们将深入探讨buffer、translog、refresh、commit、flush和merge等核心概念&#xff0c;帮助您更好地理解Elasticsearch的数据存储机制。 写入数据的基本过程 Elast…...

牛客论坛spring initializer选用的构件

spring版本&#xff1a;2.1.5.RELEASE java版本&#xff1a;8 pom文件&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-i…...

【Java程序设计】【C00385】基于(JavaWeb)Springboot的员工信息管理系统(有论文)

基于&#xff08;JavaWeb&#xff09;Springboot的员工信息管理系统 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千套毕业设计程序&#xff0c…...

【Linux进阶之路】理解UDP,成为TCP。

前言 学了TCP 和UDP之后&#xff0c;感觉UDP就像是初入职场的年轻人&#xff0c;两耳不闻 “窗外事”&#xff0c;只管尽力地把自己的事情做好&#xff0c;但收获的却是不可靠&#xff0c;而TCP更像是涉世极深的"职场老油条"&#xff0c;给人的感觉就是 “城府极深&a…...

Linux实用操作

一&#xff0c;各类小技巧&#xff08;快捷键&#xff09; 强制停止 ctrlc强制停止 Linux某些程序的运行&#xff0c;如果想要强制停止它&#xff0c;可以使用快捷键ctrlc 命令输入错误,也可以通过快捷键ctrlc,退出当前输入,重新输入 退出、登出 ctrld退出或登出 可以通过快…...

OpenJudge - 12:加密的病历单

总时间限制: 1000ms 内存限制: 65536kB 描述 小英是药学专业大三的学生&#xff0c;暑假期间获得了去医院药房实习的机会。 在药房实习期间&#xff0c;小英扎实的专业基础获得了医生的一致好评&#xff0c;得知小英在计算概论中取得过好成绩后&#xff0c;主任又额外交给她一…...

QGIS编译(跨平台编译)057:FastCGI编译(Windows、Linux、MacOS环境下编译)

文章目录 1、FastCGI介绍2、FastCGI下载3、Windows下编译4、linux下编译5、MacOS下编译1、FastCGI介绍 FCGI 是 FastCGI 的缩写,是一种用于改善 CGI(Common Gateway Interface)性能的协议。在传统的 CGI 中,每次请求都需要启动一个新的进程来处理,这导致了较高的资源消耗和…...

jenkins+newman+postman持续集成环境搭建

一、Newman简介 Newman是一款基于Node.js开发的&#xff0c;可以运用postman工具直接从命令运行和测试postman集合 二、Newman应用 环境准备&#xff1a;js/ cnpm或npm配置好环境&#xff0c;执行如下命令 三、安装newman 验证是否安装成功&#xff0c;命令&#xff1a;newm…...

取消自动设置的开机自启动(pywin32库)请勿仿照!否则可能对电脑造成损害。

本文使用创作助手。 要取消Python程序的开机自启动&#xff0c;可以通过删除注册表中相应的注册表项来实现。请按照以下步骤进行操作&#xff1a; 打开Windows注册表编辑器&#xff1a;按下 Windows R 键&#xff0c;输入 regedit&#xff0c;然后按下回车键。 导航到注册表…...

金融投贷通(金融投资+贷款通)项目准备

金融投贷通&#xff08;金融投资贷款通&#xff09;项目准备 专业术语投资专业术语本息专业术语还款专业术语项目介绍三个子系统技术架构核心流程发布借款标投资业务 项目实施测试流程测试步骤 专业术语 投资专业术语 案例&#xff1a;张三借给李四5W&#xff0c;约定期满1年后…...

跟我学C++中级篇——STL的中的删除

一、介绍 在STL中一般删除的方式有两类&#xff0c;一种是使用全局的std::remove(remove_if类似)&#xff0c;一种是使用容器自带的erase&#xff0c;前者其实并没有真正的删除数据&#xff0c;而后者则是在移动时&#xff0c;会有一些细节的处理&#xff0c;否则要么程序崩溃…...

js如何遍历查询一个颗树

近段时间去面试的时候&#xff0c;被面试官问到如何遍历查询一个颗树的时候&#xff0c;可能最近自己看了数据结构的书之后&#xff0c;隐隐约约就想到二叉树的三种排序&#xff08;前序、中序、后序&#xff09;&#xff0c;但是当时自己没有想起这三种排序的名字&#xff0c;…...

【面试必备】针对一个案例,怎么测试

思考角度 测试用例设计万能公式功能测试&#xff08;最重要&#xff09;界面测试易用性测试性能测试安全性测试兼容性测试容错性测试 常见案例物品类水杯笔 软件类微信发送朋友圈功能 测试用例设计万能公式 在面试中经常会遇到的一类题是&#xff0c;给你一个具体的产品&#…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...