每天一道leetcode:剑指 Offer 53 - II. 0~n-1中缺失的数字(适合初学者二分查找)

今日份题目:

一个长度为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 <= 数组长度 <= 10000

题目思路及代码

方法一:暴力查找

从头到尾,用一个int型数据记录数组当前位置本应为那个数,然后两者进行判断,如果不同就返回记录的数,相同就到下一个继续判断。

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

方法二:二分查找

循环遍历本应出现的所有的数,判断是否存在于数组中,如果不存在就返回这个数,如果所有数都存在,说明确实的是数组长度的那个数。二分查找可以使时耗降低。

class Solution 
{
public:bool find(vector<int>& nums,int target)//二分查找target是否在数组中{int l=0,r=nums.size()-1,n=nums.size();int mid;while(l<=r){mid=(l+r)/2;if(nums[mid]>target){r=mid-1;}else if(nums[mid]<target){l=mid+1;}else return true;}return false;}int missingNumber(vector<int>& nums) {for(int i=0;i<nums.size();i++) //遍历所有应该出现的数判断是否存在{bool cur=find(nums,i);if(cur==false) return i;}return nums.size();}
};

提交结果

暴力查找

二分查找

  欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

uniapp 返回上一页并刷新

如要刷新的是mine页面 在/pages/mine/improveInfo页面修改信息&#xff0c;点击保存后跳转到个人中心&#xff08;/pages/mine/index&#xff09;页面并刷新更新数据 点击保存按钮时执行以下代码&#xff1a; wx.switchTab({url: /pages/mine/index }) // 页面重载 let pages …

在线文本转语音播放 (TTS)

具体请前往&#xff1a;在线文本转语音播放(TTS)

彩虹云商城搭建完整教程 完整的学习资料

彩虹云商城搭建完整教程 完整的学习资料提供给大家学习 随着电子商务的快速发展&#xff0c;越来越多的企业开始意识到开设一个自己的电子商城对于销售和品牌推广的重要性。然而&#xff0c;选择一家合适的网站搭建平台和正确地构建一个商城网站并不是一件容易的事情。本文将为…

Python操作MySQL将数据库表中的数据导出到excel

Author: liukai 2810248865qq.com Date: 2022-08-18 04:28:52 LastEditors: liukai 2810248865qq.com LastEditTime: 2023-06-29 09:35:25 FilePath: \PythonProject01\Python操作MySQL数据库及excel将数据库表中的数据导出到excel中.py Description: 这是默认设置,请设置custo…

华夏ERP信息泄露

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 文章作者拥有对此文章的修改和解释权。如欲转载或传播此文章&#xff0c…

14-4_Qt 5.9 C++开发指南_QUdpSocket实现 UDP 通信_UDP组播

文章目录 1. UDP组播的特性2. UDP 组播实例程序的功能3. 组播功能的程序实现4. 源码4.1 可视化UI设计4.2 mainwindow.h4.3 mainwindow.cpp 1. UDP组播的特性 下图简单表示了组播的原理。UDP 组播是主机之间“一对一组”的通信模式&#xff0c;当多个客户端加入由一个组播地址定…

智慧工地云平台源码,基于微服务+Java+Spring Cloud +UniApp +MySql开发

智慧工地可视化系统利用物联网、人工智能、云计算、大数据、移动互联网等新一代信息技术&#xff0c;通过工地中台、三维建模服务、视频AI分析服务等技术支撑&#xff0c;实现智慧工地高精度动态仿真&#xff0c;趋势分析、预测、模拟&#xff0c;建设智能化、标准化的智慧工地…

uni-app:实现列表单选功能

效果图&#xff1a; 核心解析&#xff1a; 一、 <view class"item_all" v-for"(item, index) in info" :key"index"><view classposition parameter-info text-over :classitem.checked?"checked_parameter":""…

ubuntu 暂时不能解析域名 解决办法

需要修改系统DNS 打开终端&#xff1a;输入 sudo vi /etc/resolv.conf 回车 在打开的配置文件中添加DNS信息 nameserver 114.114.114.114 nameserver 8.8.8.8 保存退出&#xff0c;重启系统即可。

【Nacos篇】Nacos基本操作及配置

官方文档&#xff1a;https://nacos.io/zh-cn/docs/v2/ecology/use-nacos-with-spring-cloud.html 前置条件&#xff1a;SpringCloud脚手架 单机模式下的Nacos控制台&#xff1a; <dependencies><!-- Registry 注册中心相关 --><dependency><groupId>…

《golang设计模式》第一部分·创建型模式-04-抽象工厂模式(Abstract Factory)

文章目录 1. 概述1.1 角色1.2 类图 2. 代码示例2.1 设计2.2 代码2.3 类图 1. 概述 1.1 角色 AbstractFactory&#xff08;抽象工厂&#xff09;&#xff1a;它声明了一组用于创建产品的方法&#xff0c;每一个方法对应一种产品。ConcreteFactory&#xff08;具体工厂&#xf…

系统架构设计高级技能 · 软件可靠性分析与设计(三)【系统架构设计师】

系列文章目录 系统架构设计高级技能 软件架构概念、架构风格、ABSD、架构复用、DSSA&#xff08;一&#xff09;【系统架构设计师】 系统架构设计高级技能 系统质量属性与架构评估&#xff08;二&#xff09;【系统架构设计师】 系统架构设计高级技能 软件可靠性分析与设计…

HCIP 三层交换机

一、实现VLAN间通信 在传统的交换机组网中&#xff0c;默认所有网络都处于同一个广播域&#xff0c;带来了许多问题&#xff0c;VLAN技术的提出&#xff0c;满足了二层组网隔离广播域需求&#xff0c;使得属于不同的VLAN间网络无法通信&#xff0c;但不同VLAN之间又存在着互相…

MybatisPlus存在 sql 注入漏洞(CVE-2023-25330)解决办法

首先我们了解下这个漏洞是什么&#xff1f; MyBatis-Plus TenantPlugin 是 MyBatis-Plus 的一个为多租户场景而设计的插件&#xff0c;可以在 SQL 中自动添加租户 ID 来实现数据隔离功能。 MyBatis-Plus TenantPlugin 3.5.3.1及之前版本由于 TenantHandler#getTenantId 方法在…

快速排序【Java算法】

文章目录 1. 概念2. 思路3. 代码实现 1. 概念 快速排序是一种比较高效的排序算法&#xff0c;采用 “分而治之” 的思想&#xff0c;通过多次比较和交换来实现排序&#xff0c;在一趟排序中把将要排序的数据分成两个独立的部分&#xff0c;对这两部分进行排序使得其中一部分所有…

Python web实战之Django用户认证详解

关键词&#xff1a; Python Web 开发、Django、用户认证、实战案例 概要 今天来探讨一下 Django 的用户认证吧&#xff01;在这篇文章中&#xff0c;我将为大家带来一些有关 Django 用户认证的最佳实践。 1. Django 用户认证 在开发 Web 应用程序时&#xff0c;用户认证是一个…

05 Ubuntu下安装.deb安装包方式安装vscode,snap安装Jetbrains产品等常用软件

使用deb包安装类型 deb包指的其实就是debian系统&#xff0c;ubuntu系统是基于debian系统的发行版。 一般我们会到需要的软件官网下载deb安装包&#xff0c;然后你既可以采用使用“软件安装”打开的方法来进行安装&#xff0c;也可以使用命令行进行安装。我推荐后者&#xff…

Mr. Cappuccino的第58杯咖啡——MacOS配置Maven和Java环境

MacOS配置Maven和Java环境 查看Mac使用的是哪个shell下载并准备Maven下载Maven配置前准备 下载并安装JDK下载JDK安装JDK 配置Maven和Java环境添加配置加载配置 验证环境 查看Mac使用的是哪个shell echo $SHELL如果使用的是bash&#xff0c;则使用以下命令 open ~/.bash_profi…

六、ESP32数码管显示数字

1. 本节课的成功 2. 数码管 为什么会亮呢? 答:里面就是LED灯

【雕爷学编程】Arduino动手做(180)---Seeeduino Lotus开发板2

37款传感器与执行器的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&am…