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

LeetCode第四天(448. 找到所有数组中消失的数字)

给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。 

官解:

方法一:原地修改
思路及解法

我们可以用一个哈希表记录数组 nums 中的数字,由于数字范围均在[1,n] 中,记录数字后我们再利用哈希表检查[1,n] 中的每一个数是否出现,从而找到缺失的数字。

由于数字范围均在 [1,n]中,我们也可以用一个长度为n 的数组来代替哈希表。这一做法的空间复杂度是 O(n) 的。我们的目标是优化空间复杂度到O(1)。

注意到nums 的长度恰好也为 n,能否让nums 充当哈希表呢?

由于nums 的数字范围均在[1,n] 中,我们可以利用这一范围之外的数字,来表达「是否存在」的含义。

具体来说,遍历nums,每遇到一个数 x,就让 nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中,增加以后,这些数必然大于 n。最后我们遍历 nums,若 nums[i] 未大于 n,就说明没有遇到过数i+1。这样我们就找到了缺失的数字。

注意,当我们遍历到某个位置时,其中的数可能已经被增加过,因此需要对 n 取模来还原出它本来的值。

class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {int n = nums.length;for(int num : nums){//计算出它真实的位置int x = (num - 1) % n;//真实的位置上的数字+你(数组的长度)nums[x] += n;} //创建返回结果的数组List<Integer> ret = new ArrayList<Integer>();//遍历for(int i = 0;i < n;i++){//当前数组的数值小于数组长度,就说明没有这个数字if(nums[i] <= n){//就把这个数添加在数组中(为什么+1,因为i是下标,下标从0开始)ret.add(i+1);}}return ret;}
}

相关文章:

LeetCode第四天(448. 找到所有数组中消失的数字)

给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 官解&#xff1a; 方法一&#xff1a;原地修改 思路及解法 我们可以用一个哈希表记录数组 nums 中…...

【vivado】在原有工程上新建工程

一、前言 在工作中&#xff0c;我们经常需要接触到别人的工程&#xff0c;并在别人的工程上新加设计功能&#xff0c;此时我们需要以别人工程为基础新建工程。 二、在已有工程上新建工程的方法 2.1 vivado 页面file-project-save as... 该方法的优点为&#xff1a;可以直接…...

(原型与原型链)前端八股文修炼Day5

一 原型链的理解 原型链定义&#xff1a; 原型链是 JavaScript 中实现对象继承的关键机制之一&#xff0c;它是一种对象之间的关系&#xff0c;通过这种关系&#xff0c;一个对象可以继承另一个对象的属性和方法。 原型链的组成&#xff1a; 每个对象都有一个指向另一个对象的…...

逐步学习Go-并发通道chan(channel)

概述 Go的Routines并发模型是基于CSP&#xff0c;如果你看过七周七并发&#xff0c;那么你应该了解。 什么是CSP&#xff1f; "Communicating Sequential Processes"&#xff08;CSP&#xff09;这个词组的含义来自其英文直译以及在计算机科学中的使用环境。 CSP…...

鸿蒙HarmonyOS应用开发之Node-API开发规范

当传入napi_get_cb_info的argv不为nullptr时&#xff0c;argv的长度必须大于等于传入argc声明的大小。 当argv不为nullptr时&#xff0c;napi_get_cb_info会根据argc声明的数量将JS实际传入的参数写入argv。如果argc小于等于实际JS传入参数的数量&#xff0c;该接口仅会将声明…...

单例模式

文章目录 单例模式特殊类的设计单例模式饿汉模式懒汉模式懒汉VS饿汉懒汉的线程安全单例对象的释放 单例模式 认识单例模式之前先认识一下几种常见的特殊类的设计。 特殊类的设计 设计一个类 只能再堆上创建对象 只能再堆上创建&#xff0c;则通过new来创建对象。 将类的构造函…...

Android OpenMAX - 开篇

Android Media是一块非常庞大的内容&#xff0c;上到APP的书写&#xff0c;中到播放器的实现、封装格式的了解&#xff0c;下到OMX IL层的实现、Decoder的封装&#xff0c;每一块都需要我们下很大的功夫学习。除此之外&#xff0c;我们还要对一些相关的模块进行了解&#xff0c…...

ubuntu开启ssh服务

1.安装openssh-server sudo apt-get install openssh-server 2.开启服务 sudo servive ssh start 3.设置开机自启动 sudo systemctl enable ssh 4.检查是否开启成功 ps -ef | grep ssh 如使用xshell等连接时失败&#xff0c;可以尝试关闭防火墙&#xff1a; sudo sys…...

测试缺陷定位的基本方法

前后端bug特征 后端&#xff1a; 业务逻辑问题&#xff1a;如任务状态未扭转成功&#xff0c;创建任务失败等数据类问题&#xff1a;如新增的任务在页面没有展示出来等性能类问题&#xff1a;提交任务一直显示创建中、批量操作等待耗时长超时等 前端&#xff1a; 页面显示类…...

【数字图像处理matlab系列】数组索引

【数字图像处理matlab系列】数组索引 【先赞后看养成习惯】【求点赞+关注+收藏】 MATLAB 支持大量功能强大的索引方案,这些索引方案不仅简化了数组操作,而且提高了程序的运行效率。 1. 向量索引 维数为1xN的数组称为行向量。行向量中元素的存取是使用一维索引进行的。因此…...

【2024系统架构设计】案例分析- 3 数据库

目录 一 基础知识 二 真题 一 基础知识 1 ORM ORM(Object—Relationl Mapping...

vue基础——java程序员版(总集)

前言&#xff1a; ​ 这是一个java程序员的vue学习记录。 ​ vue是前端的主流框架&#xff0c;按照如今的就业形式作为后端开发的java程序员也是要有所了解的&#xff0c;下面是本人的vue学习记录&#xff0c;包括vue2的基本使用以及引入element-ui&#xff0c;使用的开发工具…...

Rancher(v2.6.3)——Rancher配置Harbor镜像仓库

Rancher配置Harbor镜像仓库详细说明文档&#xff1a;https://gitee.com/WilliamWangmy/snail-knowledge/blob/master/Rancher/Rancher%E4%BD%BF%E7%94%A8%E6%96%87%E6%A1%A3.md#8rancher%E9%85%8D%E7%BD%AEharbor ps&#xff1a;如果觉得作者写的还行&#xff0c;能够满足您的需…...

C++类和对象、面向对象编程 (OOP)

文章目录 一、封装1.抽象、封装2.类和对象(0)学习视频(1)类的构成(2)三种访问权限(3)struct和class的区别(4)私有的成员变量、共有的成员函数(5)类内可以直接访问私有成员&#xff0c;不需要经过对象 二、继承三、多态1.概念2.多态的满足条件3.多态的使用条件4.多态原理剖析5.纯…...

Introduction to Data Mining 数据挖掘

Why Data Mining? • The Explosive Growth of Data: from terabytes to petabytes — Data collection and data availability ◦ Automated data collection tools, database systems, Web, computerized society — Major sources of abundant data ◦ Business: Web, e-co…...

常用的 Git 命令

初始化一个新的仓库&#xff1a; git init 克隆一个仓库&#xff1a; git clone <仓库地址> 查看文件状态&#xff1a; git status 添加文件到暂存区&#xff1a; git add <文件名> 提交文件到仓库&#xff1a; git commit -m "提交说明" 查看提交历…...

jackson:JSON字符串(String)类型的成员序列化和反序列化

对于如下类型定义TestTaskInfo&#xff0c;props字段为JSON字符串(这在数据库经常用到),可以自由保存各种类型的数据 Data public class TestTaskInfo {private String id;private String props;public TestTaskInfo() {}public TestTaskInfo(String id, String props) {super…...

使用docker的好处???(docker的优势)

标准化环境&#xff1a; Docker通过容器技术封装应用程序及其依赖&#xff08;如库、配置文件、运行时环境等&#xff09;&#xff0c;确保应用程序在任何环境中都能以一致的方式运行。这种标准化消除了“在我机器上能运行”的问题&#xff0c;因为容器化应用能在开发、测试、生…...

Google AI 肺癌筛查的计算机辅助诊断

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

【字符串算法题记录】反转字符串中的单词(leetcode),右旋字符串(kama)——双指针以及反转的奇思妙用

反转字符串中的单词 题目链接 思考 这题的思路顺序是&#xff1a;移除多余空格&#xff08;双指针法&#xff09;——》反转整个字符串&#xff09;——》反转字符串中每个单词。 移除多余空格&#xff08;双指针法&#xff09; 因为字符串开头也可能有多个字符&#xff0…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...