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

【C++习题】24.二分查找算法_0～n-1中缺失的数字

news 来源：原创 2025/5/13 1:02:33

文章目录

    • 题目链接：
    • 题目描述：
    • 解法
    • C++ 算法代码：
    • 图解

题目链接：

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

题目描述：

fa91c9e0a51f48e60b0424775c039edc

解法

哈希表：

建立一个hash表看哪个数字出现次数为0

直接遍历找结果：

看从哪里断开了，断开的数就是我们要找的数

位运算：

异或运算，拿数组里面的数和完整的数放到一起，相同的会抵消掉。

例如：[0,1,2,4,5]和[0,1,2,3,4,5]

异或后，只剩下3

数学方法：高斯求和公式

先把没缺少的数组求和，利用等差数列公式，然后依次减去原数组的数，得到的结果就是我们缺失的数。

二分算法：

找二段性

d5d4f6a8cf0c0034d67ffccdcd36a8bc

虚线左边和下标一样，右边比下标大一。我们要找的就是虚线右边最左侧的那个数的下标。

C++ 算法代码：

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid) left = mid + 1;else right = mid;}return left == records[left] ? left + 1 : left;  }
};

图解

例如：records = [0,1,2,3,5]

c25d68c9951d5d5552dfe4d451e8c329

  1. left = 0, right = 4

    进入循环，mid = 2

    records[mid] == mid，left = 3

  2. left = 3, right = 4

    进入循环，mid = 3

    records[mid] == mid，left = 4

  3. left = 4, right = 4

    跳出循环，返回4

相关文章：

【C++习题】24.二分查找算法_0～n-1中缺失的数字

文章目录 题目链接&#xff1a;题目描述&#xff1a;解法C 算法代码&#xff1a;图解 题目链接&#xff1a; 剑指 Offer 53 - II. 0&#xff5e;n-1中缺失的数字 题目描述&#xff1a; 解法 哈希表&#xff1a; 建立一个hash表看哪个数字出现次数为0 直接遍历找结果&#xff1…...

编程日记 2025/5/13 1:02:33

分享一款内存马检测工具(附网盘链接)

DuckMemoryScan DuckMemoryScan是一款简单寻找包括不限于iis劫持,无文件木马,shellcode免杀后门的工具 功能列表 HWBP hook检测 检测线程中所有疑似被hwbp隐形挂钩内存免杀shellcode检测可疑进程检测(主要针对有逃避性质的进程[如过期签名与多各可执行区段])无文件落地木马检…...

编程日记 2025/5/12 17:58:16

vscode ctrl+/注释不了css

方式一.全部禁用插件排查问题. 方式二.打开首选项的json文件,注释掉setting.json,排查是哪一行配置有问题. 我的最终问题:需要将 "*.vue": "vue",改成"*.vue": "html", "files.associations": { // "*.vue": &qu…...

编程日记 2025/5/4 9:11:10

python数据分析之爬虫基础：爬虫介绍以及urllib详解

前言 在数据分析中&#xff0c;爬虫有着很大作用&#xff0c;可以自动爬取网页中提取的大量的数据&#xff0c;比如从电商网站手机商品信息&#xff0c;为市场分析提供数据基础。也可以补充数据集、检测动态变化等一系列作用。可以说在数据分析中有着相当大的作用&#xff01;…...

编程日记 2025/5/12 7:31:50

洛谷 P1036 [NOIP2002 普及组] 选数 C语言

题目&#xff1a;https://www.luogu.com.cn/problem/P1036 题目描述 已知 nn 个整数 x1,x2,⋯ ,xn&#xff0c;以及 1 个整数 k&#xff08;k<n&#xff09;。从 n 个整数中任选 k 个整数相加&#xff0c;可分别得到一系列的和。例如当 n4&#xff0c;k3&#xff0c;4 个…...

编程日记 2025/5/12 22:46:44

CSS动画案例4

目录 一、介绍二、基础布局1. HTML2.CSS 三、交互效果1.设置中间图片的动画2.设置左右两侧每行内容的起始位置与动画3.设置左右两侧第二行与第三行的动画延时的时间4.icon划入时的效果 四、结束语 一、介绍 今天我们继续来看下一个CSS动画案例&#xff0c;这个案例主要是图片以…...

编程日记 2025/5/12 23:06:08

华为云云连接+squid进行正向代理上网冲浪

1 概述 ‌Squid‌是一个高性能的代理缓存服务器&#xff0c;主要用于缓冲Internet数据。它支持多种协议&#xff0c;包括FTP、gopher、HTTPS和HTTP。Squid通过一个单独的、非模块化的、I/O驱动的进程来处理所有的客户端请求&#xff0c;这使得它在处理请求时具有较高的效率‌。…...

编程日记 2025/5/12 23:22:37

【C++】封装红黑树实现的map和set

前言 这篇博客我们将上篇博客实现的红黑树来封装成自己实现的set和map&#xff0c;来模拟一下库里的map和set &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;C 若有问题 评论区见&#x1f4dd; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 1.源…...

编程日记 2025/5/11 3:18:02

【SSM】mybatis的增删改查

目录 代理Dao方式的增删改查 1. 创建项目 $$1. 在sql.xml里增加日志代码以及user的mapper资源。 $$ 2. 在usermapper里引入接口。 $$3. 在测试类中引入以下代码&#xff0c;并修改其中名字。 $$ 4. 实例对象User.java里属性要与表中列严格对应。 2. 查询 1>. 查询所有 …...

编程日记 2025/5/10 20:47:51

macos下brew安装redis

首先确保已安装brew&#xff0c;接下来搜索资源&#xff0c;在终端输入如下命令&#xff1a; brew search redis 演示如下&#xff1a; 如上看到有redis资源&#xff0c;下面进行安装&#xff0c;执行下面的命令&#xff1a; brew install redis 演示效果如下&#xff1a; …...

编程日记 2025/5/12 23:13:12

鸿蒙修饰符

文章目录 一、引言1.1 什么是修饰符1.2 修饰符在鸿蒙开发中的重要性1.3 修饰符的作用机制 二、UI装饰类修饰符2.1 Styles修饰符2.1.1 基本概念和使用场景2.1.2 使用示例2.1.3 最佳实践 2.2 Extend修饰符2.2.1 基本概念2.2.2 使用示例2.2.3 Extend vs Styles 对比2.2.4 使用建议…...

编程日记 2025/5/13 0:32:32

【Linux】Linux2.6内核进程调度队列与调度原理

目录 一、进程管理中的部分概念二、寄存器三、进程切换四、Linux2.6内核进程调度队列与调度原理结尾 一、进程管理中的部分概念 竞争性: 系统进程数目众多&#xff0c;而CPU资源只有少量&#xff0c;甚至1个&#xff0c;所以进程之间是具有竞争属性的。为了高效完成任务&#…...

编程日记 2025/5/13 0:28:31

MacOS使用VSCode编写C++程序如何配置clang编译环境

前言 这段时间在练习写C和Python&#xff0c;用vscode这个开发工具&#xff0c;调试的时候遇到一些麻烦&#xff0c;浪费了很多时间&#xff0c;因此整理了这个文档。将详细的细节描述清楚&#xff0c;避免与我遇到同样问题的人踩坑。 1.开发环境的配置 vscode的开发环境配置…...

编程日记 2025/5/12 23:57:46

【Spark源码分析】规则框架- `analysis`分析阶段使用的规则

analysis分析阶段使用的规则 规则批策略规则说明SubstitutionfixedPointOptimizeUpdateFields该规则优化了 UpdateFields 表达式链&#xff0c;因此看起来更像优化规则。但是&#xff0c;在处理深嵌套模式时&#xff0c;UpdateFields 表达式树可能会非常复杂&#xff0c;导致分…...

编程日记 2025/5/12 23:38:08

Windows和Ubuntu系统下cmake和opencv的安装和使用

以下是在Windows和Ubuntu系统下分别安装CMake并使用C配置OpenCV实现读取图片并显示功能的详细步骤&#xff1a; Windows系统 1. 安装CMake 访问CMake官方网站&#xff08;https://cmake.org/download/&#xff09;。根据你的Windows系统版本&#xff08;32位或64位&#xff…...

编程日记 2025/5/10 6:14:10

详解 Qt QtPDF之QPdfPageNavigator 页面跳转

文章目录 前言头文件&#xff1a; 自 Qt 6.4 起继承自&#xff1a; 属性backAvailable : const boolcurrentLocation : const QPointFcurrentPage : const intcurrentZoom : const qrealforwardAvailable : const bool 公共函数QPdfPageNavigator(QObject *parent)virtual ~QPd…...

编程日记 2025/5/12 23:00:33

设计模式之单例

单例可以说是设计模式中最简单的一种模式。但任何一种设计模式都是普遍经验的总结&#xff0c;都有值得思考的地方。所以单例也并不简单&#xff0c;下面让我们慢慢了解它。 单例顾名思义这个类只有一个实例。要做到这点&#xff0c;需要做到以下几点&#xff1a; &#xff08;…...

编程日记 2025/5/13 0:53:06

笔记软件：我来、思源笔记、Obsidian、OneNote

最近wolai的会员到期了&#xff0c;促使我更新了一下笔记软件。 首先&#xff0c;wolai作为一个笔记软件&#xff0c;我觉得有很多做得不错的方面&#xff08;否则我也不会为它付费2年了&#xff09;&#xff0c;各种功能集成得很全&#xff08;公式识别这个功能我写论文的时候…...

编程日记 2025/5/12 23:14:24

前端入门指南：前端模块有哪些格式？分别什么情况使用

前言 在当今的前端开发中&#xff0c;模块化是提升代码组织性和可维护性的关键手段。随着前端技术的发展&#xff0c;出现了多种模块化方案&#xff0c;每种方案都有其独特的优势和适用场景。本文将详细探讨常见的前端模块格式&#xff0c;包括全局变量、IIFE、CommonJS、AMD、…...

编程日记 2025/5/12 23:30:52

Vue3 常用指令解析：v-bind、v-if、v-for、v-show、v-model

Vue 是一个非常强大的前端框架&#xff0c;提供了许多常用指令来简化模板的使用。Vue 指令以 v- 开头&#xff0c;用于对 DOM 元素和组件的行为进行控制。本文将介绍 Vue 中常见的五个指令&#xff1a;v-bind、v-if、v-for、v-show 和 v-model&#xff0c;并通过实例代码来演示…...

编程日记 2025/5/13 0:54:12

如何查看ubuntu服务器的ssh服务是否可用

你可以通过以下几种方法检查 Ubuntu 服务器上的 SSH 服务是否可用&#xff1a; 1. 使用 systemctl 检查 SSH 服务状态 首先&#xff0c;检查 SSH 服务是否正在运行&#xff1a; sudo systemctl status ssh如果 SSH 服务正在运行&#xff0c;你会看到类似以下的输出&#xff…...

编程日记 2025/5/13 0:09:37

redis面试复习

1.redis是单线程还是多线程 无论什么版本工作线程就是是一个&#xff0c;6.x高版本出现了IO多线程 单线程满足redis的串行原子&#xff0c;只不过IO多线程后&#xff0c;把输入/输出放到更多的线程里区并行&#xff0c;好处&#xff1a; 1.执行的时间更短&#xff0c;更快&a…...

编程日记 2025/5/12 11:23:17

【人工智能基础04】线性模型

文章目录 一. 基本知识1. 线性回归1.1. 基本形式1.2. 线性回归 2. 优化方法&#xff1a;梯度下降法2.1. 梯度下降法的直观意义2.2. 随机梯度下降法 3. 分类问题3.1. 二分类&#xff1a;逻辑回归-sigmoid函数3.2. 多分类问题--softmax函数 4. 岭回归与套索回归4.1. 基础概念什么…...

编程日记 2025/5/8 6:17:04

使用YOLO系列txt目标检测标签的滑窗切割：批量处理图像和标签的实用工具

使用YOLO系列txt目标检测标签的滑窗切割&#xff1a;批量处理图像和标签的实用工具 使用YOLO的TXT目标检测标签的滑窗切割&#xff1a;批量处理图像和标签的实用工具背景1. 代码概述2. 滑窗切割算法原理滑窗切割步骤&#xff1a;示例&#xff1a; 3. **代码实现**1. **加载标签…...

编程日记 2025/5/12 22:53:05

《装甲车内气体检测“神器”:上海松柏 K-5S 电化学传感器模组详解》

《装甲车内气体检测“神器”:上海松柏 K-5S 电化学传感器模组详解》 一、引言二、K-5S 电化学传感器模组概述&#xff08;一&#xff09;产品简介&#xff08;二&#xff09;产品特点&#xff08;三&#xff09;产品适用场景 三、电化学传感器原理及优点&#xff08;一&#xf…...

编程日记 2025/5/13 0:00:06

【笔记】文明、现代化与价值投资

文章目录 价值投资与理性思考资管行业特点及对从业人员的道德底线要求价值投资长期来看&#xff0c;各项资产的走势投资与投机 对文明的认知对文明的计量方式狩猎文明或1.0文明农业畜牧文明或2.0文明农业文明的天花板及三次冲顶农业文明中的思想革命和制度创新 科技文明或3.0文…...

编程日记 2025/5/12 22:48:51

排序学习整理（1）

1.排序的概念及运用 1.1概念 排序&#xff1a;所谓排序&#xff0c;就是使⼀串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作&#xff0c;以便更容易查找、组织或分析数据。 1.2运用 购物筛选排序 院校排名 1.3常见排序算法 2.实…...

编程日记 2025/5/13 0:10:39

提升分布式系统响应速度：分布式系统远程调用性能提升之道

目录 一、远程调用直接案例分析 二、并行调用 &#xff08;一&#xff09;核心思想 &#xff08;二&#xff09;并行调用的实现方式 1. 基本思路 2. 代码示例 3. 关键点说明 4.线程池配置建议 三、数据异构 &#xff08;一&#xff09;场景重提 &#xff08;二&…...

编程日记 2025/5/12 22:52:02

通过MinIO+h2non/imaginary 搭建自己的阿里云OSS

安装MinIO Docker部署MinIO对象存储服务 图片访问地址&#xff1a;http://192.168.153.138:9000/public/su7_1.jpg 安装h2non/imaginary Docker部署h2non/imaginary 处理图片地址&#xff1a;http://192.168.153.138:7000/resize?urlhttp://192.168.153.138:9000/public/su…...

编程日记 2025/5/12 23:18:03

.NET 9 AOT的突破 - 支持老旧Win7与XP环境

引言 随着技术的不断进步&#xff0c;微软的.NET 框架在每次迭代中都带来了令人惊喜的新特性。在.NET 9 版本中&#xff0c;一个特别引人注目的亮点是 AOT&#xff08; Ahead-of-Time&#xff09;支持&#xff0c;它允许开发人员将应用程序在编译阶段就优化为能够在老旧的 Win…...

编程日记 2025/5/12 23:41:29

iOS与Windows间传文件

想用数据线从 windows 手提电脑传文件入 iPhone&#xff0c;有点迂回。 参考 [1]&#xff0c;要在 windows 装 Apple Devices。装完、打开、插线之后会检测到手机&#xff0c;界面&#xff1a; 点左侧栏「文件」&#xff0c;不是就直接可以传&#xff0c;而是要通过某个应用传…...

编程日记 2025/5/12 23:02:46

ospf协议（动态路由协议）

ospf基本概念 定义 OSPF 是典型的链路状态路由协议&#xff0c;是目前业内使用非常广泛的 IGP 协议之一。 目前针对 IPv4 协议使用的是 OSPF Version 2 &#xff08; RFC2328 &#xff09;&#xff1b;针对 IPv6 协议使用 OSPF Version 3 &#xff08; RFC2740 &#xff09;。…...

编程日记 2025/5/8 5:31:14

直击高频编程考点：聚焦新版综合编程能力考查汇总

目录 一、业务性编程和广度能力考查 &#xff08;一&#xff09;基本定义 &#xff08;二&#xff09;必要性分析 二、高频考查样题&#xff08;编程扩展问法&#xff09; 考题1: 用java 代码实现一个死锁用例&#xff0c;说说怎么解决死锁问题&#xff1f;&#xff08;高…...

编程日记 2025/5/9 18:01:57

爬虫框架快速入门——Scrapy

适用人群&#xff1a;零基础、对网络爬虫有兴趣但不知道从何开始的小白。 什么是 Scrapy&#xff1f; Scrapy 是一个基于 Python 的网络爬虫框架&#xff0c;它能帮助你快速爬取网站上的数据&#xff0c;并将数据保存到文件或数据库中。 特点&#xff1a; 高效&#xff1a;支…...

编程日记 2025/5/12 23:57:46

Springfox、Swagger 和 Springdoc

Springfox、Swagger 和 Springdoc 是用于在 Spring Boot 项目中生成 API 文档的工具&#xff0c;但它们之间有显著的区别和演进关系&#xff1a; 1. Swagger 简介 Swagger 是一个开源项目&#xff0c;旨在为 RESTful APIs 提供交互式文档。最早由 SmartBear 开发&#xff0c;…...

编程日记 2025/5/12 10:24:25

Css、less和Sass（SCSS）的区别详解

文章目录 Css、less和Sass&#xff08;SCSS&#xff09;的区别详解一、引言二、CSS 简介1.1、CSS 示例 三、Less 简介2.1、Less 特性2.2、Less 示例 四、Sass&#xff08;SCSS&#xff09;简介3.1、Sass 特性3.2、SCSS 示例 五、总结 Css、less和Sass&#xff08;SCSS&#xff…...

编程日记 2025/5/12 22:59:30

新能源汽车充电基础设施短板问题多，如何实现高效、综合、智能化管理？

随着城市经济的发展&#xff0c;人民生活水平的提升&#xff0c;新能源汽车保有量快速增长&#xff0c;而日益增长的新能源汽车需求与充电基础设施建设不平衡的矛盾日益突出。由于停车泊位充电基础设施总量不足、布局待优化、利用效率低、建设运营存在短板问题等原因&#xff0…...

编程日记 2025/5/13 0:45:04

DBA面试题-1

面临失业&#xff0c;整理一下面试题&#xff0c;找下家继续搬砖 主要参考&#xff1a;https://www.csdn.net/?spm1001.2101.3001.4476 略有修改 一、mysql有哪些数据类型 1&#xff0c; 整形 tinyint,smallint,medumint,int,bigint&#xff1b;分别占用1字节、2字节、3字节…...

编程日记 2025/5/12 22:52:02

LAN,WAN,VLAN,WLAN,VPN了解笔记

局域网LAN---公司的内部网络就是局域网LAN。 提供有线连接的接口允许局域网内的设备&#xff08;如台式电脑、网络打印机、网络存储设备等&#xff09;通过以太网线连接到路由器并与其他局域网设备进行通信实现设备之间的数据传输和资源共享一种私有的网络相对其他网络传输速度…...

编程日记 2025/5/7 23:34:24

1.2 算法和算法评价

1.2.1 算法的基本概念 算法&#xff1a;对特定问题求解步骤的一种描述&#xff0c;它是指令的有限序列&#xff0c;其中的每条指令表示一个或多个操作。 算法的五个重要特性 “好”的算法的五个目标 1.2.2 算法效率的度量 一、时间复杂度 算法的时间复杂度是指一个算法每行…...

编程日记 2025/5/12 8:01:57

各大常见编程语言应用领域

不同编程语言因其特性和设计目标而适用于不同的应用领域。以下是一些常见编程语言及其主要应用领域&#xff1a; 1. Python 数据科学与人工智能&#xff1a;Python 在数据分析、机器学习、深度学习等领域广泛使用&#xff0c;因其丰富的库&#xff08;如 NumPy、Pandas、Tens…...

编程日记 2025/5/6 14:07:44

【FFT】数据点数是否一定为2的n次方？不补零会如何处理？

一般来说&#xff0c;FFT的数据点个数为以2为基数的整数次方&#xff08;采用以2为基的FFT算法&#xff0c;可以提升运算性能&#xff09;&#xff0c;但是并没有要求FFT的数据点个数一定为2的n次方。 因此针对数据点数不是以2为基数的整数次方&#xff0c;有两种处理方法&…...

编程日记 2025/5/12 23:38:08

shell脚本小练习#003:查找并拷贝目录

实例1&#xff1a; # 从当前执行脚本的路径位置开始向上搜索一个名为sourceProject目录名 # 并将这个文件目录的路径名称打印出来#!/bin/bashfunction find_dir() {local current_dir$PWDwhile [[ $current_dir ! "/" ]]; doif [[ -d "${current_dir}/sourcePr…...

编程日记 2025/5/1 12:35:49

frp内网穿透

目录 1&#xff0c;准备公网服务器 2&#xff0c;下载安装frp服务端 3&#xff0c;服务端安装 2&#xff09;编辑服务端配置文件fprs.toml 3&#xff09;配置启动服务 4&#xff09;启动服务 5 &#xff09;设置开机启动服务 6&#xff09;查看服务启动状态 3&#xff0c…...

编程日记 2025/5/12 22:50:59

Android电视项目焦点跨层级流转

1. 背景 在智家电视项目中&#xff0c;主要操作方式不是触摸&#xff0c;而是遥控器&#xff0c;通过Focus进行移动&#xff0c;确定点击进行的交互&#xff0c;所以在电视项目中焦点、选中、确定、返回这几个交互比较重要。由于电视屏比较大&#xff0c;在一些复杂页面中会存…...

编程日记 2025/5/12 22:38:17

时频转换 | Matlab基于S变换S-transform一维数据转二维图像方法

目录 基本介绍程序设计参考资料获取方式基本介绍 时频转换 | Matlab基于S变换S-transform一维数据转二维图像方法 程序设计 clear clc % close all load x.mat % 导入数据 x =...

编程日记 2025/5/13 0:20:02

转载 为nautilus安装rabbitvcs

# 添加 rabbitvcs 的 ppa 源 sudo add-apt-repository ppa:rabbitvcs/ppa sudo apt update # 安装 rabbitvcs sudo apt install rabbitvcs-cli rabbitvcs-core rabbitvcs-gedit rabbitvcs-nautilus # 注销后重新登录&#xff0c;右键即可使用 # 解决 RabbitVCS 无法自动保存…...

编程日记 2025/5/13 0:43:56

OpenCV 模板匹配全解析：从单模板到多模板的实战指南

简介&#xff1a;本文深入探讨 OpenCV 中的模板匹配技术。详细介绍构建输入图像与模板图像的步骤&#xff0c;包括读取、截取、滤波与存储等操作。剖析 cv2.matchTemplate 语法及其参数含义&#xff0c;阐述不同匹配方法下结果值的意义。同时讲解 cv2.minMaxLoc 语法&#xff0…...

编程日记 2025/5/5 13:00:03

手机控制载货汽车一键启动无钥匙进入广泛应用

移动管家载货汽车一键启动无钥匙进入手机控车系统‌&#xff0c; 该系统广泛应用于物流运输、工程作业等货车场景&#xff0c;为车主提供了高效、便捷的启动和熄火解决方案&#xff0c;体现了科技进步对物流行业的积极影响‌ 核心功能‌&#xff1a;简化启动流程&#xff0c;提…...

编程日记 2025/5/5 7:06:26

Springboot——SseEmitter流式输出

文章目录 前言SseEmitter 简介测试demo注意点异常一 ResponseBodyEmitter is already set complete 前言 最近做AI类的开发&#xff0c;看到各大AI模型的输出方式都是采取的一种EventStream的方式实现。 不是通常的等接口处理完成后&#xff0c;一次性返回。 而是片段式的处理…...

编程日记 2025/5/10 5:42:48