当前位置: 首页 > 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;给你一个具体的产品&#…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

内存分配函数malloc kmalloc vmalloc

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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...