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

消失的数字(每日一题)

目录

一、题目描述

二、题目分析

2.1 方法一

2.1.1 思路

2.1.2 代码

2.2 方法二

2.2.1 思路

2.2.2 代码

2.3 方法三

2.3.1 思路

2.3.2 代码

三、完整代码


一、题目描述

oj链接:https://leetcode.cn/problems/missing-number-lcci

     数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

示例 1:

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


示例 2:

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

二、题目分析

     此题目要求算法在O(N)时间内完成,也就是说时间复杂度不超过O(N),我们要找出数组nums中缺少的数有以下几种办法:

2.1 方法一

2.1.1 思路

     方法一主要是通过求和相减找出0-n中缺失的那个数,先将0到n之间的数相加求和,然后依次减去数组中的每个数,得到的就是缺失的那个数。

     注意这里求0到n的数相加的和我们使用了等差数列的求和公式:sum(和) = (n+1)*n/2.

     方法一的时间复杂度是:O(N),我们要将0到n的和依次减去数组中的元素,所以在这里我们需要遍历一遍数组,即执行n次循环,所以时间复杂度是O(N),他的空间复杂度是:O(1),这个算法只额外开辟了几个变量,属于是常数阶,用O(1)来表示空间复杂度。

2.1.2 代码

int missingNumberTwo(int* nums, int n)
{int sum = n * (n + 1) / 2;int i = 0;for (i = 0; i < n; i++){sum -= nums[i];}return sum;
}

2.2 方法二

2.2.1 思路

     方法二主要是通过异或找出0-n中缺失的那个数,在之前的博客:<操作符详解>中具体对异或进行了解释,如果不太清楚可以去看看。

     对于任何一个数和0异或得到的都是他本身一个数和自己异或得到的是0,并且异或是满足交换律的,因此根据这一规律,我们就可以找到0-n中缺失的那个数,先将定义一个变量x将他初始化为0,让他先和数组中的每个数进行异或操作,然后再与0到n的每个数进行异或操作,如果某个数在数组中和0-n中都存在,异或之后为0,如果有单独的一个数只在0-n中存在,而不在数组中,异或之后也无法消去,将0分别与数组中的数以及0-n之间的数异或,最后得到的就是缺失的那个数。

     方法二的时间复杂度是:O(N),我们要将0分别与数组中的数以及0-n之间的数异或,需要遍历一次数组和依次0-n之间的数,即执行2n次循环,所以时间复杂度是O(N),他的空间复杂度是:O(1),这个算法只额外开辟了几个变量,属于是常数阶,用O(1)来表示空间复杂度。

2.2.2 代码

int missingNumberOne(int* nums, int n)
{int x = 0;for (int i = 0; i < n; i++){x ^= nums[i];}for (int i = 0; i < n + 1; i++){x ^= i;}return x;
}

2.3 方法三

2.3.1 思路

     方法三主要是先对数组进行排序处理,然后使用二分查找,在这里对数组排序我们使用的是qsort库函数,使用qsort库函数还要提供一个比较函数compar。

     方法三的时间复杂度是:O(N*logN),在这个算法中,我们要求时间复杂度,分开来看,二分查找的时间复杂度是O(logN),qsort的时间复杂度是O(N*logN),按照大O的渐进表示法,此算法的时间复杂度是O(N*logN)。

     注意题目中要求时间复杂度不超过O(N),所以这个思路在力扣上不会通过,仅仅提供一种参考思路。

2.3.2 代码

int compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i = 0;for (i = 0; i <= n; i++){int exchange = 1;int begin = 0;int end = n - 1;while (begin <= end){ int mid = (begin + end) / 2;if (i > nums[mid])begin = mid + 1;else if (i < nums[mid])end = mid - 1;else{exchange = 0;break;}}if (exchange == 1){return i;}}
}

三、完整代码

     这道题是属于oj类型的题目,所以在拿到vs上编译的时候,需要自己写一个主函数,在这里我们提供一个完整的函数。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>int compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberOne(int* nums, int n)
{int x = 0;for (int i = 0; i < n; i++){x ^= nums[i];}for (int i = 0; i < n + 1; i++){x ^= i;}return x;
}int missingNumberTwo(int* nums, int n)
{int sum = n * (n + 1) / 2;int i = 0;for (i = 0; i < n; i++){sum -= nums[i];}return sum;
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i = 0;for (i = 0; i <= n; i++){int exchange = 1;int begin = 0;int end = n - 1;while (begin <= end){ int mid = (begin + end) / 2;if (i > nums[mid])begin = mid + 1;else if (i < nums[mid])end = mid - 1;else{exchange = 0;break;}}if (exchange == 1){return i;}}
}int main()
{int nums[5] = { 0 };int i = 0;int n = sizeof(nums) / sizeof(nums[0]);for (i = 0; i < n ; i++){scanf("%d", &nums[i]);}//1.异或int x = missingNumberOne(nums, n);printf("%d\n", x);//2.求和再相减x = missingNumberTwo(nums, n);printf("%d\n", x);//3.排序+二分查找x = missingNumberThree(nums, n);printf("%d\n", x);return  0;
}



 

相关文章:

消失的数字(每日一题)

目录 一、题目描述 二、题目分析 2.1 方法一 2.1.1 思路 2.1.2 代码 2.2 方法二 2.2.1 思路 2.2.2 代码 2.3 方法三 2.3.1 思路 2.3.2 代码 三、完整代码 一、题目描述 oj链接&#xff1a;https://leetcode.cn/problems/missing-number-lcci 数组nums包含从0到n的…...

TypeScript算法基础——TS字符串的常用操作总结:substring、indexOf、slice、replace等

字符串的操作是算法题当中经常碰见的一类题目&#xff0c;主要考察对string类型的处理和运用。 在处理字符串的时候&#xff0c;我们经常会碰到求字符串长度、匹配子字符串、替换字符串内容、连接字符串、提取字符串字符等操作&#xff0c;那么调用一些简单好用的api可以让工作…...

Leetcode100-两数之和

参见官方题解 一、学到的知识 正面寻找两个数之和相加等于某个数&#xff0c;如 ab c&#xff0c;不如反过来寻找 a c - b 正面寻找需要两层 for 循环&#xff0c;把每个数都进行遍历&#xff0c;所以时间复杂度较高 反过来则可以通过维护一个 a 的集合&#xff0c;每次通过…...

4565: 删除中间的*

描述规定输入的字符串中只包含字母和*号&#xff0c;除了字符串前导和尾部的*号之外,将串中其他*号全部删除输入输入数据包括一串字符串&#xff0c;只包含字母和*&#xff0c;总长度不超过80。输出输出删除中间*后的字符串。样例输入*******A*BC*DEF*G****样例输出*******ABCD…...

VUE组件示例说明

<!-- * Author: xxx.xx * Date: 2021-07-20 14:33:41 * LastEditors: xxx.xx * LastEditTime: 2021-07-20 18:22:37 * PageTitle: 上拉加载组件 * Description: 描述... * FilePath: /wxapp-view/components/loadmore.vue --> <template><view class"c-mor…...

Widget中的State-学习笔记

Widget 有 StatelessWidget 和 StatefulWidget 两种类型。StatefulWidget 应对有交互、需要动态变化视觉效果的场景&#xff0c;而 StatelessWidget 则用于处理静态的、无状态的视图展示。StatefulWidget 的场景已经完全覆盖了 StatelessWidget&#xff0c;因此我们在构建界面时…...

股市实战技巧(知行合一)

投资策略 长线&#xff1a;优质核心股票大仓位核心标的票&#xff0c;小仓位短线投资投机小储蓄可加大投机仓位价值投资也要去做仓位控制 行情好&#xff0c;总体大仓位&#xff0c;行情小&#xff0c;小仓位个股根据走势调整个股仓位&#xff08;布林线的20%原则&#xff09;…...

k8s-资源限制-探针检查

文章目录一、资源限制1、资源限制的使用2、reuqest资源&#xff08;请求&#xff09;和limit资源&#xff08;约束&#xff09;3、Pod和容器的资源请求和限制4、官方文档示例5、资源限制实操5.1 编写yaml资源配置清单5.2 释放内存&#xff08;node节点&#xff0c;以node01为例…...

一文让你彻底了解Linux内核文件系统

一&#xff0c;文件系统特点 文件系统要有严格的组织形式&#xff0c;使得文件能够以块为单位进行存储。文件系统中也要有索引区&#xff0c;用来方便查找一个文件分成的多个块都存放在了什么位置。如果文件系统中有的文件是热点文件&#xff0c;近期经常被读取和写入&#xf…...

解决前端组件下拉框选择功能失效问题

问题&#xff1a; 页面下拉框选择功能失效 现象&#xff1a; 在下拉框有默认值的情况下&#xff0c;点击下拉框的其他值&#xff0c;发现并没有切换到其他值 但是在下拉框没默认值的情况下&#xff0c;功能就正常 原因 select 已经绑定选项&#xff08;有默认值&#xff09; 在…...

Linux_vim编辑器入门级详细教程

前言&#xff08;1&#xff09;vim编辑器其实本质上就是对文本进行编辑&#xff0c;比如在.c文件中改写程序&#xff0c;在.txt文件写笔记什么的。一般来说&#xff0c;我们可以在windows上对文本进行编译&#xff0c;然后上传给Linux。但是有时候我们可能只是对文本进行简单的…...

TCP 的演化史-TCP 是一个过渡

TCP 诞生于 1970 年代早期&#xff0c;彼时没有分组交换网的大规模应用&#xff0c;彼时绝大多数通信都在使用电话&#xff0c;电报&#xff0c;电挂等电路交换技术。 诞生在这种环境下的技术不可能脱离时代的影响&#xff0c;如果一个孩子出生在一个父母关系冷漠的家庭&#x…...

Flask

Flask第三方组件非常全&#xff0c;适合小型 API服务类项目&#xff0c;但第三方组件运行稳定性相对Django差。 基础知识 Flask安装 pip install flask2.0.3Flask库文件 Jinjia2&#xff1a;模板渲染库Markupsafe&#xff1a;返回安全标签 只要Flask返回模板或者标签时都会…...

SAP系统与MES系统的数据协同技术方案

1&#xff0e;MES介绍 本文中提到的MES系统是在西门子公司的SIMATIC IT平台上开发完成。所有的应用子系统进行统一分析、统一设计、统一开发&#xff0c;利用统一的开发平台和数据库系统&#xff0c;保证了管理系统的集成性、高效性。 2&#xff0e;数据协同接口包含的…...

2018年蓝桥杯省赛试题-5道(Python)

文章目录一、日志统计思考二、递增三元组思考三、螺旋折线思考四、乘积最大思考五、全球变暖思考尾声提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、日志统计 题目描述 小明维护着一个程序员论坛。 现在他收集了一份"点赞"日志&#xf…...

Python稀疏矩阵最小二乘法

文章目录最小二乘法返回值测试最小二乘法 scipy.sparse.linalg实现了两种稀疏矩阵最小二乘法lsqr和lsmr&#xff0c;前者是经典算法&#xff0c;后者来自斯坦福优化实验室&#xff0c;据称可以比lsqr更快收敛。 这两个函数可以求解AxbAxbAxb&#xff0c;或arg min⁡x∥Ax−b…...

mac本前端Homebrew下载,操作

1、打开电脑终端 2、下载Homebrew&#xff0c;在终端中输入 /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"开始下载Homebrew&#xff0c;因为这个地址是国外网站&#xff0c;下载失败的话&#xff0c;输入…...

Linux系统之查看进程监听端口方法

Linux系统之查看进程监听端口方法一、端口监听介绍二、使用netstat命令1.netstat命令介绍2.netstat帮助3.安装netstat工具4.列出所有监听 tcp 端口5.显示TCP端口的统计信息6.查看某个服务监听端口三、使用ss命令1.ss命令介绍2.ss命令帮助3.查看某个服务监听端口四、使用lsof命令…...

使用命令别名一键启动arthas

1. 使用命令别名启动arthas 确保单板上有jdk和arthas jdk目录&#xff1a;/home/xinliushijian/arthas/jdk arthas目录&#xff1b;/home/xinliushijian/arthas su xinliushijian编写脚本messi.sh cd /home/xinliushijian/arthas vi messi.sh 内容如下&#xff1a; #!/bin/ba…...

python+pytest接口自动化(2)-HTTP协议基础

HTTP协议简介HTTP 即 HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09;&#xff0c;是互联网上应用最为广泛的一种网络协议。所有的 WWW 文件都必须遵守这个标准。设计 HTTP 最初的目的是为了提供一种发布和接收 HTML 页面的方法。HTTP 协议在 OSI 模型中属…...

操作系统权限提升(十五)之绕过UAC提权-基于白名单DLL劫持绕过UAC提权

系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权 操作系统权限提升(十四)之绕过UAC提权-基于白名单AutoElevate绕过UAC提权 注&#xff1a;阅读本编文章前&#xff0c;请先阅读系列文章&#xff0c;以…...

非常好看的html网页个人简历

一. 前言 文末获取gitee链接 在前几天逛b站的时候&#xff0c;发现了个比较实用的东西-----个人简介网页版&#xff0c;相当于网页版的个人简历&#xff0c;相较于PDF形式的&#xff0c;网页版所能呈现内容更加丰富&#xff0c;而且更加美观&#xff0c;在BOOS上被HR小姐姐要…...

轻量级网络模型ShuffleNet V2

在学习ShuffleNet V2内容前需要简单了解卷积神经网络和MobileNet,以及Shuffnet V1的相关内容&#xff0c;大家可以出门左转&#xff0c;去看我之前的几篇博客MobileNet发展脉络&#xff08;V1-V2-V3&#xff09;&#xff0c;轻量级网络模型ShuffleNet V1&#x1f197;&#xff…...

分享美容美发会员管理系统功能的特点_美容美发会员管理系统怎么做

人们越来越关心美发&#xff0c;美发行业发展迅速&#xff0c;小程序可以连接在线场景&#xff0c;许多美发院也开发了会员卡管理系统。那么一个实用的美发会员管理系统怎么制作呢&#xff1f;它有什么功能&#xff1f;我们一起来看看~&#xff08;干货满满&#xff0c;耐心看完…...

Oracle-05-DCL篇

🏆一、简介 Oracle的DCL代表数据库控制语言,用于管理数据库对象的访问和安全性。DCL的两个主要命令是GRANT和REVOKE。 GRANT命令用于授予用户或角色对数据库对象的访问权限,例如表、视图或存储过程。GRANT命令的语法如下: GRANT privilege_name [, privilege_name]... …...

tess4j简单使用入门

tess4j下载 下载地址: https://sourceforge.net/projects/tess4j/ 不要直接下载,点击files,然后下载最新版 下载解压后放到指定的目录即可,这里放到d:\jar目录下 tess4j根目录: d:\jar\tess4j tess4j使用 把test4j项目目录中dist和lib目录下的所有jar包导入到需要的项目中…...

WebGPU学习(4)---使用 UniformBuffer

接下来让我们使用 UniformBuffer。UniformBuffer 是一个只读内存区域&#xff0c;可以在着色器上访问。 这次&#xff0c;我们将传递给着色器的矩阵存储在 UniformBuffer 中。演示示例 1.在顶点着色器中的 UniformBuffer 这次我们在顶点着色器里定义一个名为Uniforms的新结构体…...

Http客户端Feign-远程调用

Feign的使用步骤 引入依赖添加EnableFeignClients注解编写FeignClient接口使用FeignClient中定义的方法代替RestTemplate Feign的日志配置 1.方式一是配置文件&#xff0c;feign.client.config.xxx.loggerLevel 如果xxx是default则代表全局如果xxx是服务名称,例如userservi…...

RK3568镜像的拆包和打包

文章目录 前言一、window上分包和打包分包打包二、Linux上分包和打包分包打包总结前言 本文记录在win10上利用瑞芯微提供的工具进行分包和打包,同样也有Linux教程 提示:以下是本篇文章正文内容,下面案例可供参考 一、window上分包和打包 分包 window下一般直接利用工具即…...

《设计模式》适配器模式

《设计模式》适配器模式 适配器&#xff08;Adapter&#xff09;是一种结构型设计模式&#xff0c;它允许我们将一个类的接口转换成另一个类的接口&#xff0c;从而使得原本由于接口不兼容而无法合作的类能够一起工作。适配器模式通常用于以下情况&#xff1a; 在已有的类中添…...