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

( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

❓645. 错误的集合

难度:简单

集合 s 包含从 1n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

示例 1:

输入:nums = [1,2,2,4]
输出:[2,3]

示例 2:

输入:nums = [1,1]
输出:[1,2]

提示:

  • 2 < = n u m s . l e n g t h < = 1 0 4 2 <= nums.length <= 10^4 2<=nums.length<=104
  • 1 < = n u m s [ i ] < = 1 0 4 1 <= nums[i] <= 10^4 1<=nums[i]<=104

💡思路:

法一:交换数组元素

最直接的方法是先对数组进行排序,这种方法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。本题可以以 O ( n ) O(n) O(n) 的时间复杂度、 O ( 1 ) O(1) O(1) 空间复杂度来求解。

  • 主要思想是通过交换数组元素使得数组上的元素在正确的位置上
  • 这样只有 重复的数 出现在 丢失整数 的位置上。

法二:哈希表

重复的数字在数组中出现 2 次,丢失的数字在数组中出现 0次,其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中是否出现

  • 如果出现两次,则找到了重复的数
  • 将所有数都存到哈希表,再遍历哈希表,则可找到丢失的数

🍁代码:(Java、C++)

法一:交换数组元素
Java

class Solution {public int[] findErrorNums(int[] nums) {for(int i = 0; i < nums.length; i++){while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){swap(nums, i, nums[i] - 1);}}for(int i = 1; i <= nums.length; i++){if(nums[i - 1] != i){return new int[]{nums[i - 1], i};}}return null;}private void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

C++

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {for(int i = 0; i < nums.size(); i++){while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){swap(nums, i, nums[i] - 1);}}for(int i = 1; i <= nums.size(); i++){if(nums[i - 1] != i){return {nums[i - 1], i};}}return {};}void swap(vector<int>& nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
};

法二:哈希表
Java

class Solution {public int[] findErrorNums(int[] nums) {HashSet<Integer> s = new HashSet<>();int repeat = 0, lose = 0;for(int num : nums){if(s.contains(num)) repeat = num;s.add(num);}for(int i = 1; i <= nums.length; i++){if(!s.contains(i)){lose = i;break;}}return new int[]{repeat, lose};}
}

C++

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {unordered_set<int> s;int repeat = 0, lose = 0;for(int num : nums){if(s.find(num) != s.end()) repeat = num;s.insert(num);}for(int i = 1; i <= nums.size(); i++){if(s.find(i) == s.end()){lose = i;break;}}return {repeat, lose};}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),法一只需常量级空间;而哈希表需要创建大小为 O ( n ) O(n) O(n) 的哈希表,空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

❓645. 错误的集合 难度&#xff1a;简单 集合 s 包含从 1 到 n 的整数。不幸的是&#xff0c;因为数据错误&#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值&#xff0c;导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了…...

2023年全国最新道路运输从业人员精选真题及答案63

百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 119.在危险货物道路运输过程中&#xff0c;&#xff08;&#x…...

Kettle安装与使用

一、Kettle简介 Kettle最早是一个开源的ETL&#xff08;Extract-Transform-Load的缩写&#xff09;工具&#xff0c;全称为KDE Extraction, Transportation, Transformation and Loading Environment。后来Kettle重命名为Pentaho Data Integration 。它由Java开发&#xff0c;…...

C51 - DS18B20

Thermometer 1> 实验概述2> 硬件设计3> DS18B203.1> 原理框图3.2> 数据格式 4> 单总线&#xff08;1-Wire&#xff09;通讯协议4.1> 初始化&#xff08;复位&#xff09;时序4.2> 写-DS18B20时序4.3> 读-DS18B20时序4.4> 命令 5> 程序设计5.1…...

手把手教你使用vue2搭建微前端micro-app

​ 简述 本文主要讲述新手小白怎么搭建micro-app&#xff0c;几乎是每一步都有截图说明。上手应该很简单。 研究背景 这段时间在网上找了很多有关微前端相关的知识&#xff0c;起初本来是想着先搭建一个single-spa&#xff0c;但是奈何网上能找到的内容都是千篇一律。我也是…...

DDR3(MIG核配置官方demoFPGA代码实现及仿真)

由于直接对 DDR3 进行控制很复杂&#xff0c;因此一般使用 MIG IP 来实现&#xff0c;同时为了更简单地使用 MIG IP&#xff0c;我们采用 AXI4 总线协议进行控制。下面首先介绍 MIG IP 的配置&#xff0c;然后看看官方 demo &#xff08;里面包含一个仿真要用到的 DDR3 模型&am…...

传奇人物《周兴和》书连载之67 不辱神圣的使命

不辱神圣的使命 这里&#xff0c;先前还是一个十分神秘的地方。 外人和车辆要想进入这片区域&#xff0c;那是绝对不允许的。这片区域隐于群山之中&#xff0c;且戒备森严&#xff0c;外人若想进入&#xff0c;那是要经过好几道政治审查和随身检查的。近年来&#xff0c;随着…...

Spring框架中的单例Beans是线程安全的么?

在Spring框架中&#xff0c;单例Beans默认是线程安全的。 当你在Spring框架中声明一个单例Bean并配置为默认的单例作用域时&#xff0c;Spring会确保对该Bean的并发访问是线程安全的。以下是一个简单的代码演示&#xff1a; 假设我们有一个名为 SingletonBean 的单例 Bean 类…...

AI脚本插件开发-链接图自动建立档名-插件制作源码-illustrator插件开发

文章目录 1.illustrator1.1.app.activeDocument1.2.selection2.模块分析3.源码工程4.功能描述5.作者答疑本文主要分析一款插件的源码,链接图自动建立档名,代码一般较长,读者耐心阅读,对于学习插件开发具有不小的帮助。先介绍了一下基础资料,如有不懂的地方,就去这些资料里…...

rust智能指针

智能指针 智能指针虽然也号称指针&#xff0c;但是它是一个复杂的家伙&#xff1a;通过比引用更复杂的数据结构&#xff0c;包含比引用更多的信息&#xff0c;例如元数据&#xff0c;当前长度&#xff0c;最大可用长度等。引用和智能指针的另一个不同在于前者仅仅是借用了数据…...

Git、Gitee、Github、Gitlab区别与联系

Git&#xff1a;本地软件&#xff0c;无需联网即可使用&#xff0c;实现本地代码的管理。 分布式版本控制系统&#xff0c;是一种工具&#xff0c;用于代码的存储和版本控制。 将本地文件通过一定的操作将其同步上传到Github或Gitee Gitee&#xff1a;是一家中…...

接口优化的策略

1.批处理 批量思想&#xff1a;批量操作数据库&#xff0c;这个很好理解&#xff0c;我们在循环插入场景的接口中&#xff0c;可以在批处理执行完成后一次性插入或更新数据库&#xff0c;避免多次IO。 //批量入库 batchInsert();List的安全操作有以下几种方式&#xff1a; 使…...

android 隐藏底部虚拟按键

方法一 滑动屏幕 可重新显示出来 protected void hideBottomUIMenu() { //隐藏虚拟按键&#xff0c;并且全屏 if (Build.VERSION.SDK_INT <11 && Build.VERSION.SDK_INT < 19) { // lower api View v this.getWindow().getDecorView(); v.setSyst…...

基于电流控制的并网逆变器(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

learn_C_deep_9 (汇编角度理解return的含义、const 的各种应用场景)

return 关键字 不知道我们大家是否有一个疑惑&#xff1a;我们下载一个大型游戏软件&#xff08;王者荣耀&#xff09;&#xff0c;都要花几个小时去下载&#xff0c;但是一旦我们游戏连输&#xff0c;想要删除这个软件的时候&#xff0c;它仅仅只需要十几秒&#xff0c;这是为…...

基于深度学习的OCR技术

随着数字化时代的到来&#xff0c;图片识别技术越来越受到人们的关注。其中&#xff0c;OCR技术作为图片处理的一个重要分支&#xff0c;可以将扫描的图片进行自动识别和分类&#xff0c;极大地提高了工作效率。本文将介绍有道实况OCR技术的相关内容&#xff0c;帮助读者更好地…...

『python爬虫』09. bs4实战之下载精美壁纸(保姆级图文)

目录 爬取思路代码思路1.拿到主页面的源代码. 然后提取到子页面的链接地址, href2.通过href拿到子页面的内容. 从子页面中找到图片的下载地址 img -> src3.下载图片 3. 完整实现代码总结 欢迎关注 『python爬虫』 专栏&#xff0c;持续更新中 欢迎关注 『python爬虫』 专栏&…...

【Linux学习】多线程——线程控制 | 线程TCB

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 线程控制 | 线程TCB &#x1f9f0;线程控制&#x1f3b4;线程创建&#x1f3b4;线程结束&#x1…...

Node 10 接口

接口 简介 接口是什么 接口是 前后端通信的桥梁 简单理解&#xff1a;一个接口就是 服务中的一个路由规则 &#xff0c;根据请求响应结果 接口的英文单词是 API (Application Program Interface)&#xff0c;所以有时也称之为 API 接口 这里的接口指的是『数据接口』&#…...

大型互联网企业大流量高并发电商领域核心项目已上线(完整流程+项目白皮书)

说在前面的话 面对近年来网络的飞速发展&#xff0c;大家已经都习惯了网络购物&#xff0c;从而出现了一些衍生品例如&#xff1a;某宝/某东/拼夕夕等大型网站以及购物APP~ 并且从而导致很多大型互联网企业以及中小厂都需要有完整的项目经验&#xff0c;以及优秀处理超大流量…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...