当前位置: 首页 > 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…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

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

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

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...