( 位运算 ) 268. 丢失的数字 ——【Leetcode每日一题】

❓268. 丢失的数字

难度:简单

给定一个包含 [0, n]n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1:

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示:

  • n == nums.length
  • 1 < = n < = 1 0 4 1 <= n <= 10^4 1<=n<=104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

进阶: 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

💡思路:

基础知识必知:位运算基本原理

仅用线性复杂度和额外常数空间,基本上就是使用位运算了!

两个相同的数异或的结果为 0

  • 所有数以及数组下标 [0, n] 进行异或操作,最后的结果就是单独出现的那个数。

🍁代码:(Java、C++)

Java

class Solution {
    public int missingNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < nums.length; i++){
            ans = ans ^ (i + 1) ^ nums[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            ans = ans ^ (i + 1) ^ nums[i];
        }
        return ans;
    }
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/18293.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

干货分享|一款让企业知识管理变得简单高效的工具软件

互联网发展到下半场&#xff0c;很多企业都开始进行数字化转型&#xff0c;在这个过程中&#xff0c;很多企业都忽视了极为重要的一点——企业的知识管理。如今信息化的时代&#xff0c;可以说企业的知识管理是引领企业数字化转型、进行创新的关键。 企业知识管理的实质就是对…

视频文本检索之CLIP4Clip

论文&#xff1a;CLIP4Clip: An Empirical Study of CLIP for End to End Video Clip Retrieval GitHub&#xff1a;https://github.com/ArrowLuo/CLIP4Clip 学习是一种行动反射&#xff0c; 不是为了晓得些“知识”&#xff0c; 要切己体察&#xff0c;代入自己&#xff0c…

mid360激光雷达跑Point-LIO算法

在商场里面上下楼穿梭,使用mid360激光雷达,完成建图 以下是建图的运行过程及参数配置 mid360激光雷达驱动 安装(ubuntu20.4 ) /ws_livox/src/livox_ros_driver2$source /opt/ros/noetic/setup.sh /ws_livox/src/livox_ros_driver2$./build.sh ROS1配置修改MID360_confi…

可拓展哈希

可拓展哈希 借CMU 15445的ppt截图来说明问题。 我们传统静态hash的过程是hash函数后直接将值存入对应的bucket&#xff0c;但是在可扩展hash中&#xff0c;得查询Directory&#xff08;左&#xff09;&#xff0c;存入directory指向的bucket&#xff08;右&#xff09;。 下面…

ASEMI代理ADI亚德诺LTC6992IS6-1#TRMPBF车规级芯片

编辑-Z LTC6992IS6-1#TRMPBF参数描述&#xff1a; 型号&#xff1a;LTC6992IS6-1#TRMPBF 输出频率&#xff1a;3.81Hz 工作电源电压范围&#xff1a;2.25 - 5.5V 通电复位电压&#xff1a;1.95V 电源电流&#xff1a;105-365A SET引脚处的电压&#xff1a;1V 频率设置电…

物联网|IAR集成开发环境简介|cc254核心板硬件资源|物联网之蓝牙4.0 BLE基础-学习笔记(3)

文章目录 4、IAR集成开发环境简介5、 cc254核心板硬件资源 4、IAR集成开发环境简介 完整稳定的专业嵌入式开发环境&#xff0c;对不同的处理器有统一的用户界面&#xff0c;支持35种以上的MCU&#xff0c;包括8&#xff0c;16&#xff0c;32位&#xff0c; 完全兼容C语言的 高…

FPN和PAN的内容及区别

FPN和PAN都是用于解决在目标检测中特征金字塔网络(FPN)在多尺度检测任务上的不足的方法。下面分别详细介绍一下它们的原理和区别。 FPN FPN全称Feature Pyramid Network&#xff0c;是由FAIR在2017年提出的一种处理多尺度问题的方法。FPN的主要思路是通过构建金字塔式的特征图…

【CSS系列】第四章 · CSS字体属性

写在前面 Hello大家好&#xff0c; 我是【麟-小白】&#xff0c;一位软件工程专业的学生&#xff0c;喜好计算机知识。希望大家能够一起学习进步呀&#xff01;本人是一名在读大学生&#xff0c;专业水平有限&#xff0c;如发现错误或不足之处&#xff0c;请多多指正&#xff0…

人机智能中几个困难问题浅析

1、人机之间与人人之间信任的区别人机之间的信任与人人之间的信任存在以下异同&#xff1a;①信任对象。人机之间的信任的对象是计算机系统、算法、机器人等&#xff0c;而人人之间的信任的对象是其他人。②信任方式。人机之间的信任是基于技术、安全协议等建立的&#xff0c;例…

【Linux网络】传输层中UDP和TCP协议

文章目录 1、再谈端口号2、UDP协议3、TCP协议3.1 TCP协议段格式3.2 TCP的三次握手和四次挥手&#xff08;连接管理机制&#xff09;3.3 TCP的滑动窗口3.4 TCP的流量控制3.5 拥塞控制3.6 延迟应答和捎带应答3.7 面向字节流和粘包问题3.8 TCP总结 1、再谈端口号 端口号port标识一…

2023年前端面试题汇总-代码输出篇

1. 异步 & 事件循环 1. 代码输出结果 const promise new Promise((resolve, reject) > {console.log(1);console.log(2); }); promise.then(() > {console.log(3); }); console.log(4); 输出结果如下&#xff1a; 1 2 4 promise.then 是微任务&#xff0c;它…

1、防刷限流实现1

1、本章诉求 限流的需求出现在许多常见的场景中&#xff1a; 秒杀活动&#xff0c;有人使用软件恶意刷单抢货&#xff0c;需要限流防止机器参与活动某api被各式各样系统广泛调用&#xff0c;严重消耗网络、内存等资源&#xff0c;需要合理限流 2、流程设计 3、方案实现 3.1…

使用 spring 的 IoC 的实现账户的CRUD(2)双层实现

spring实现service和dao的数据的查找 dao层设置接口实现dao层的接口service设置接口通过注入dao层&#xff0c;来实现接口 //dao层的接口&#xff0c;定义了根据id查询的方法 public interface Accountdao {Account findByid(int id); }实现接口&#xff1a;实现了查询的方法 …

项目创建第一天 搭建前端环境

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、环境是什么&#xff1f;二、使用步骤1.前台搭建方式1.创建项目2.目录结构3. 安装elementui4. 创建路由5.使用axios6.bug记录6.1出现跨域问题6.2 解决方式6.…

2023年会展服务研究报告

第一章 行业概况 会展行业是指一系列与会议、展览、展示相关的服务和经济活动的总称&#xff0c;是加强企业间交流、促进合作和推动经济发展的重要手段。该行业涉及广泛&#xff0c;包括会议和展览的组织、场地租赁和设计、活动策划和执行、展品运输和咨询服务等各个环节。随着…

tiechui_lesson03_缓冲读写与自定义控制

学习了与应用层通过缓冲区方式的交互&#xff0c;包括读写&#xff0c;自定义控制等。小坑比较多&#xff0c;大部分是是头文件和设置上的错误&#xff0c;跟着视频敲想快进就跳过了一些细节。包括&#xff1a; <windef.h> 头文件的引用 //使用DWORD等类型switch语句…

基于标签的协同过滤算法实现与个人兴趣相关的文章推荐

一、前言 在当前信息爆炸的时代&#xff0c;每天都会涌现出大量的文章&#xff0c;人们有时候会感到信息的获取难度比筛选更大。而作为信息的提供者&#xff0c;我们应当为用户提供依据个人兴趣的文章推荐。 本项目中的文章标签相似度推荐功能使用了一种基于标签的协同过滤算…

Java版本的工程项目管理系统源代码之工程项目管理系统面临的挑战

​ ​工程项目管理系统是指从事工程项目管理的企业&#xff08;以下简称工程项目管理企业&#xff09;受业主委托&#xff0c;按照合同约定&#xff0c;代表业主对工程项目的组织实施进行全过程或若干阶段的管理和服务。 ​系统定义 工程项目管理企业不直接与该工程项目的总承包…

易视腾iS-E5-NGH_3798MV100_MT7601_卡刷固件包_当贝纯净桌面

易视腾iS-E5-NGH_3798MV100_MT7601_卡刷固件包_当贝纯净桌面 特点&#xff1a; 1、适用于对应型号的电视盒子刷机&#xff1b; 2、开放原厂固件屏蔽的市场安装和u盘安装apk&#xff1b; 3、修改dns&#xff0c;三网通用&#xff1b; 4、大量精简内置的没用的软件&#xff0…

产品经理 - 原型图设计软件

原型图设计软件哪个好用&#xff1f;6款好用软件推荐&#xff01; - 知乎 原型图都可以用什么软件做&#xff1f;11款好用软件分享&#xff01; 摩客, 墨刀 2014 墨刀是A股上市公司万兴科技旗下的在线一体化产品设计协作平台 即时设计是一款支持在线协作的专业级 UI 设计工…