剑指 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 入…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...
