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

剑指 Offer 53 - II. 0~n-1中缺失的数字

原题链接

难度:easy\color{Green}{easy}easy


题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制:

1<=数组长度<=100001 <= 数组长度 <= 100001<=数组长度<=10000


算法1

(二分)

  • 排序数组中的搜索问题,首先想到 二分法 解决,排序数组使用双指针也是高频选项~
  • 根据题意,数组可以按照以下规则划分为两部分。
    • 左子数组 nums[mid] == mid
    • 右子数组 nums[mid != mid
  • 缺失的数字等于 “右子数组的首位元素” 对应的索引;
    在这里插入图片描述
    在这里插入图片描述

复杂度分析

  • 时间复杂度O(logn)O(logn)O(logn)

  • 空间复杂度 : O(1)O(1)O(1)

C++ 代码

class Solution {
public:int missingNumber(vector<int>& nums) {// 特判 特殊情况if (nums.empty()) return 0;int n = nums.size() + 1;if (nums.back() == n - 2) return n - 1;int l = 0, r = n - 2;while (l < r) {int mid = (l + r) / 2;if (nums[mid] != mid) r = mid;else l = mid + 1;}return l;}
};

算法2

(哈希)

首先遍历数组 nums,将数组中的每个元素加入哈希集合,然后依次检查从 0 到 n−1 的每个整数是否在哈希集合中,不在哈希集合中的数字即为缺失的数字。

复杂度分析

  • 时间复杂度O(n)O(n)O(n)

  • 空间复杂度 : O(n)O(n)O(n)

C++ 代码

class Solution {
public:int missingNumber(vector<int>& nums) {unordered_set<int> hash;int n = nums.size() + 1;for (int i = 0; i < nums.size(); i ++) {hash.insert(nums[i]);}int missing = -1;for (int i = 0; i <= n - 1; i ++) {if (!hash.count(i)) {missing = i;break;}}return missing;}
};

相关文章:

剑指 Offer 53 - II. 0~n-1中缺失的数字

原题链接 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 一个长度为n-1的递增排序数组中的所有数字都是唯一的&#xff0c;并且每个数字都在范围0&#xff5e;n-1之内。在范围0&#xff5e;n-1内的n个数字中有且只有一个数字不在该数组中&#xff0c;请找出这个数字…...

分布式id

一、分布式系统 1.1 分布式系统的定义和应用场景 分布式系统是由多个独立的计算机节点协同工作&#xff0c;以共同完成一个任务的系统。这些节点通过网络进行通信和协调&#xff0c;共享计算和存储资源&#xff0c;从而实现对更大规模问题的处理和更高系统可用性的要求。 分…...

创意编程py模拟题

前言&#xff1a;好久没写博客了&#xff0c;来水好好写一篇 注&#xff1a;本篇文章为py&#xff0c;不是c 1、敲七 版本1 题目&#xff1a; 题目描述 输出7和7的倍数&#xff0c;还有包含7的数字例如&#xff08;17&#xff0c;27&#xff0c;37…70&#xff0c;71&#…...

uniapp中条件编译

官方&#xff1a;https://uniapp.dcloud.net.cn/tutorial/platform.html#%E8%B7%A8%E7%AB%AF%E5%85%BC%E5%AE%B9 #ifndef H5 代码段… #endif 表示除了H5其他都可以编译 #ifdef H5 代码段… #endef 表示只能编译H5&#xff0c;其他的都不能编译 其他编译平台请查看官方文档。 …...

封装 YoloV5 detect.py 成 Python 库以供 python 程序使用

本项目地址 Github 本项目地址 Github Introduction YoloV5 作为 YoloV4 之后的改进型&#xff0c;在算法上做出了优化&#xff0c;检测的性能得到了一定的提升。其特点之一就是权重文件非常的小&#xff0c;可以在一些配置更低的移动设备上运行&#xff0c;且提高速度的同时…...

PostgreSQL , PostGIS , 球坐标 , 平面坐标 , 球面距离 , 平面距离

标签 PostgreSQL , PostGIS , 球坐标 , 平面坐标 , 球面距离 , 平面距离 背景 PostGIS中有两种常用的空间类型geometry和geography&#xff0c;这两种数据类型有什么差异&#xff0c;应该如何选择&#xff1f; 对于GIS来说&#xff0c;首先是坐标系&#xff0c;有两种&#…...

K3S 系列文章-5G IoT 网关设备 POD 访问报错 DNS ‘i/o timeout‘分析与解决

开篇 《K3s 系列文章》《Rancher 系列文章》 问题概述 20220606 5G IoT 网关设备同时安装 K3S Server, 但是 POD 却无法访问互联网地址&#xff0c;查看 CoreDNS 日志提示如下&#xff1a; ... [ERROR] plugin/errors: 2 update.traefik.io. A: read udp 10.42.0.3:38545-&…...

社会工程学介绍

目录前言手段和术语假托在线聊天/电话钓鱼下饵&#xff08;Baiting&#xff09;等价交换同情心尾随&#xff08;Tailgating or Piggybacking&#xff09;社交工程学的演进钓鱼式攻击电脑蠕虫垃圾邮件特别人物总结前言 在信息安全方面&#xff0c;社会工程学是指对人进行心理操…...

干货 | 有哪些安慰剂按钮的设计?

仔细观察我们的生活&#xff0c;你会发现处处都是安慰剂按钮&#xff0c;ATM的点钞声、开启空调的呼呼声&#xff0c;这些都对用户心里产生了有意的引导作用&#xff0c;当你打开了空调按钮&#xff0c;先播放声音会让你感觉你按下的按钮起到了作用。 我们的大脑不喜欢杂乱无章…...

LeetCode 每日一题 2023/2/13-2023/2/19

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录2/13 1234. 替换子串得到平衡字符串2/14 1124. 表现良好的最长时间段2/15 1250. 检查「好数组」2/16 2341. 数组能形成多少数对2/17 1139. 最大的以 1 为边界的正方形2/18 1…...

SAP 关于多种语言配置

怎样才能在登录时选择自己需要的语言登录呢&#xff1f;虽然这个问题对很多人来说可能根本就算不上问题&#xff0c;但对很多新手来说可能却是很想尽快解决的问题。 曾经有位Puber说有个很简单的办法&#xff0c;但可惜的是在我一直没找到这个办法。今天看到一份资料&#xff…...

万字长文讲述由ChatGPT反思大语言模型的技术精要

文&#xff5c;张俊林 源&#xff5c;知乎张俊林 导读&#xff1a;ChatGPT出现后惊喜或惊醒了很多人。惊喜是因为没想到大型语言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;效果能好成这样&#xff1b;惊醒是顿悟到我们对LLM的认知及发展理念&#xff0c…...

SpringBoot静态资源访问

静态资源路径 类路径下&#xff1a;/resources/static/、/resources/public/、/resources/resources/、/resources/META-INF/resources 这些路径下的资源均可直接访问&#xff1b;通过 http://ip:port/资源名称 访问即可 可在配置文件中对访问路径和访问拦截规则进行设置&…...

【物联网】智慧农业病虫害精准辨识竞赛思路及代码分享

来源&#xff1a;投稿 作者&#xff1a;LSC 编辑&#xff1a;学姐 比赛官网: https://www.dataglobal.cn/cmpt/signUpInfo200.html 任务描述 请参赛者设计智慧农业病虫害检测系统&#xff0c;给出一体化问题解决方案&#xff0c;鼓励参赛选手结合某一果园/农作物实际情况建立…...

Properties类读取配置文件

文章目录前言一、Properties类的使用 :1、创建sk.properties文件2、编写读取 properties 属性文件&#xff0c;并输出属性值。3、运行结果总结前言 Properties类的介绍 : 在Java中提供了 java.util.Properties 类&#xff0c;来读取 .properties 属性文件。在程序调用 Propert…...

知其然更要知其所以然,聊聊SQLite软件架构

SQLite是一个非常受欢迎的数据库&#xff0c;在数据库排行榜中已经进入前十的行列。这主要是因为该数据库非常小巧&#xff0c;而且可以支持Linux、Windows、iOS和Andriod的主流的操作系统。 SQLite非常简单&#xff0c;是一个进程内的动态库数据库。其最大的特点是可以支持不同…...

微服务架构的演变

文章目录1.1 系统架构的演变过程1.1.1 单体应用架构1.1.2 垂直应用架构1.1.3 分布式架构1.1.4 SOA架构1.1.5 微服务架构1.2 微服务架构设计原则1.2.1 AKF拆分原则1.2.1.1 X轴扩展&#xff08;水平复制&#xff09;1.2.1.2 Y轴扩展&#xff08;模块拆分&#xff09;1.2.1.3 Z轴扩…...

使用html-to-image代替html2canvas,结合jspdf实现下载pdf(下载截图下载前端dom元素)

一、问题 一开始的时候&#xff0c;准备使用html2canvasjspdf来实现的&#xff0c;但是遇到了一个麻烦的问题&#xff0c;在其他项目中使用html2canvas没有任何问题&#xff0c;但是在要开发的项目中使用&#xff0c;就给我报错&#xff0c;是真滴烦。 html2canvas报错 Uncau…...

云环境渗透测试的重要性

&#x1f315;写在前面 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; ✉️今日分享&#xff1a; “在这个世上&#xff0c;除了极稀少的例外&#xff0c;我们其实只有两种选择&#xff1a;要么是孤独&#xff0c;要么就是庸俗。” 随着云计…...

ROS2 入门应用 请求和应答(Python)

ROS2 入门应用 请求和应答&#xff08;Python&#xff09;1. 创建功能包1. 创建功能包2. 创建源文件2.1. 服务端2.2. 客户端3. 添加依赖关系4. 添加入口点5. 编译和运行1. 创建功能包 1. 创建功能包 在《ROS2 入门应用 工作空间》中已创建和加载了ros2_ws工作空间 在《ROS2 入…...

为什么你的USB设备总接触不良?A/B型接口物理结构对比与耐久性测试

为什么你的USB设备总接触不良&#xff1f;A/B型接口物理结构对比与耐久性测试 每次给手机充电都要反复调整角度&#xff0c;打印机线稍微碰一下就断开连接——这些恼人的USB接口问题&#xff0c;本质上都是物理结构设计的差异在作祟。作为消费电子领域最基础的连接标准&#xf…...

Java高频面试题:RocketMQ有哪些使用场景?

大家好&#xff0c;我是锋哥。今天分享关于【Java高频面试题&#xff1a;RocketMQ有哪些使用场景&#xff1f;】面试题 。希望对大家有帮助&#xff1b;Java高频面试题&#xff1a;RocketMQ有哪些使用场景&#xff1f;RocketMQ 是阿里巴巴开源的一款分布式消息中间件&#xff0…...

HY-Motion 1.0保姆级教程:解决CUDA OOM、Prompt截断等常见问题

HY-Motion 1.0保姆级教程&#xff1a;解决CUDA OOM、Prompt截断等常见问题 1. 前言&#xff1a;为什么需要这篇教程 你是不是也遇到过这样的情况&#xff1a;好不容易下载了HY-Motion 1.0这个强大的3D动作生成模型&#xff0c;准备大展身手&#xff0c;结果一运行就遇到CUDA内…...

保姆级教程:用 Modelfile 快速部署 ModelScope 的 GGUF 模型到 Ollama(以 DeepSeek 为例)

从零到一&#xff1a;用Modelfile高效部署ModelScope的GGUF模型至Ollama实战指南 在本地运行大语言模型正成为开发者探索AI边界的新常态。不同于直接调用云端API&#xff0c;本地部署能带来数据隐私保障、响应速度提升以及模型深度定制等独特优势。Ollama作为轻量级模型运行框架…...

SDMatte与前端Vue.js结合:打造交互式在线抠图工具

SDMatte与前端Vue.js结合&#xff1a;打造交互式在线抠图工具 1. 引言&#xff1a;让抠图变得简单高效 想象一下这样的场景&#xff1a;电商运营每天需要处理上百张商品图片&#xff0c;设计师反复在Photoshop里手动抠图&#xff0c;自媒体创作者为找不到合适的透明背景素材发…...

League-Toolkit英雄联盟辅助工具完全指南:从配置到精通的高效使用手册

League-Toolkit英雄联盟辅助工具完全指南&#xff1a;从配置到精通的高效使用手册 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit …...

给CUDA新手的3DGS代码导读:从forward.cu到backward.cu,一步步拆解渲染流程

给CUDA新手的3DGS代码导读&#xff1a;从forward.cu到backward.cu&#xff0c;一步步拆解渲染流程 第一次看到3D Gaussian Splatting&#xff08;3DGS&#xff09;的CUDA代码时&#xff0c;我盯着那些复杂的核函数和内存操作发了半小时呆。作为从PyTorch转型过来的研究者&#…...

JVM堆内存泄漏排查:从-Xmx设置到hprof文件分析的完整避坑指南

JVM堆内存泄漏排查&#xff1a;从参数配置到实战分析的完整方法论 最近在排查一个线上服务的内存泄漏问题时&#xff0c;我发现很多开发者对JVM内存问题的处理还停留在"遇到OOM就重启服务"的初级阶段。实际上&#xff0c;一套系统化的内存排查方法论不仅能快速定位问…...

最完整的llm-graph-builder入门指南:从安装到知识图谱可视化

最完整的llm-graph-builder入门指南&#xff1a;从安装到知识图谱可视化 【免费下载链接】llm-graph-builder Neo4j graph construction from unstructured data 项目地址: https://gitcode.com/GitHub_Trending/ll/llm-graph-builder 你还在为非结构化数据转化为结构化…...

BilibiliDown:B站音视频资源管理的全场景解决方案

BilibiliDown&#xff1a;B站音视频资源管理的全场景解决方案 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors/bi/Bi…...