剑指 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中缺失的数字
原题链接 难度:easy\color{Green}{easy}easy 题目描述 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字…...
分布式id
一、分布式系统 1.1 分布式系统的定义和应用场景 分布式系统是由多个独立的计算机节点协同工作,以共同完成一个任务的系统。这些节点通过网络进行通信和协调,共享计算和存储资源,从而实现对更大规模问题的处理和更高系统可用性的要求。 分…...
创意编程py模拟题
前言:好久没写博客了,来水好好写一篇 注:本篇文章为py,不是c 1、敲七 版本1 题目: 题目描述 输出7和7的倍数,还有包含7的数字例如(17,27,37…70,71&#…...
uniapp中条件编译
官方: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,其他的都不能编译 其他编译平台请查看官方文档。 …...
封装 YoloV5 detect.py 成 Python 库以供 python 程序使用
本项目地址 Github 本项目地址 Github Introduction YoloV5 作为 YoloV4 之后的改进型,在算法上做出了优化,检测的性能得到了一定的提升。其特点之一就是权重文件非常的小,可以在一些配置更低的移动设备上运行,且提高速度的同时…...
PostgreSQL , PostGIS , 球坐标 , 平面坐标 , 球面距离 , 平面距离
标签 PostgreSQL , PostGIS , 球坐标 , 平面坐标 , 球面距离 , 平面距离 背景 PostGIS中有两种常用的空间类型geometry和geography,这两种数据类型有什么差异,应该如何选择? 对于GIS来说,首先是坐标系,有两种&#…...
K3S 系列文章-5G IoT 网关设备 POD 访问报错 DNS ‘i/o timeout‘分析与解决
开篇 《K3s 系列文章》《Rancher 系列文章》 问题概述 20220606 5G IoT 网关设备同时安装 K3S Server, 但是 POD 却无法访问互联网地址,查看 CoreDNS 日志提示如下: ... [ERROR] plugin/errors: 2 update.traefik.io. A: read udp 10.42.0.3:38545-&…...
社会工程学介绍
目录前言手段和术语假托在线聊天/电话钓鱼下饵(Baiting)等价交换同情心尾随(Tailgating or Piggybacking)社交工程学的演进钓鱼式攻击电脑蠕虫垃圾邮件特别人物总结前言 在信息安全方面,社会工程学是指对人进行心理操…...
干货 | 有哪些安慰剂按钮的设计?
仔细观察我们的生活,你会发现处处都是安慰剂按钮,ATM的点钞声、开启空调的呼呼声,这些都对用户心里产生了有意的引导作用,当你打开了空调按钮,先播放声音会让你感觉你按下的按钮起到了作用。 我们的大脑不喜欢杂乱无章…...
LeetCode 每日一题 2023/2/13-2023/2/19
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 目录2/13 1234. 替换子串得到平衡字符串2/14 1124. 表现良好的最长时间段2/15 1250. 检查「好数组」2/16 2341. 数组能形成多少数对2/17 1139. 最大的以 1 为边界的正方形2/18 1…...
SAP 关于多种语言配置
怎样才能在登录时选择自己需要的语言登录呢?虽然这个问题对很多人来说可能根本就算不上问题,但对很多新手来说可能却是很想尽快解决的问题。 曾经有位Puber说有个很简单的办法,但可惜的是在我一直没找到这个办法。今天看到一份资料ÿ…...
万字长文讲述由ChatGPT反思大语言模型的技术精要
文|张俊林 源|知乎张俊林 导读:ChatGPT出现后惊喜或惊醒了很多人。惊喜是因为没想到大型语言模型(LLM,Large Language Model)效果能好成这样;惊醒是顿悟到我们对LLM的认知及发展理念,…...
SpringBoot静态资源访问
静态资源路径 类路径下:/resources/static/、/resources/public/、/resources/resources/、/resources/META-INF/resources 这些路径下的资源均可直接访问;通过 http://ip:port/资源名称 访问即可 可在配置文件中对访问路径和访问拦截规则进行设置&…...
【物联网】智慧农业病虫害精准辨识竞赛思路及代码分享
来源:投稿 作者:LSC 编辑:学姐 比赛官网: https://www.dataglobal.cn/cmpt/signUpInfo200.html 任务描述 请参赛者设计智慧农业病虫害检测系统,给出一体化问题解决方案,鼓励参赛选手结合某一果园/农作物实际情况建立…...
Properties类读取配置文件
文章目录前言一、Properties类的使用 :1、创建sk.properties文件2、编写读取 properties 属性文件,并输出属性值。3、运行结果总结前言 Properties类的介绍 : 在Java中提供了 java.util.Properties 类,来读取 .properties 属性文件。在程序调用 Propert…...
知其然更要知其所以然,聊聊SQLite软件架构
SQLite是一个非常受欢迎的数据库,在数据库排行榜中已经进入前十的行列。这主要是因为该数据库非常小巧,而且可以支持Linux、Windows、iOS和Andriod的主流的操作系统。 SQLite非常简单,是一个进程内的动态库数据库。其最大的特点是可以支持不同…...
微服务架构的演变
文章目录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轴扩展(水平复制)1.2.1.2 Y轴扩展(模块拆分)1.2.1.3 Z轴扩…...
使用html-to-image代替html2canvas,结合jspdf实现下载pdf(下载截图下载前端dom元素)
一、问题 一开始的时候,准备使用html2canvasjspdf来实现的,但是遇到了一个麻烦的问题,在其他项目中使用html2canvas没有任何问题,但是在要开发的项目中使用,就给我报错,是真滴烦。 html2canvas报错 Uncau…...
云环境渗透测试的重要性
🌕写在前面 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 ✉️今日分享: “在这个世上,除了极稀少的例外,我们其实只有两种选择:要么是孤独,要么就是庸俗。” 随着云计…...
ROS2 入门应用 请求和应答(Python)
ROS2 入门应用 请求和应答(Python)1. 创建功能包1. 创建功能包2. 创建源文件2.1. 服务端2.2. 客户端3. 添加依赖关系4. 添加入口点5. 编译和运行1. 创建功能包 1. 创建功能包 在《ROS2 入门应用 工作空间》中已创建和加载了ros2_ws工作空间 在《ROS2 入…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
