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

【Leetcode】消失的数字 [C语言实现]

👻内容专栏:《Leetcode刷题专栏》

🐨本文概括: 面试17.04.消失的数字

🐼本文作者:花 碟

🐸发布时间:2023.4.10

目录

思想1:先排序再查找

思想2:异或运算

代码实现: 

思想3:等差数列求和相减

代码实现: 


 

点击跳转到Leetcode的OJ平台 17.04 消失的数字  

题目:

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

int missingNumber(int* nums, int numsSize);

示例1:

 示例2:

 分析:

1.数组中经过排列后是一串有序列的整数,只不过序列中缺失了一个整数,题目需要让你找出这个缺失的数字

2.时间复杂度要求允许在O(n)范围内

思想1:先排序再查找

首先,我们就可以想到将数组nums里的元素进行排序,然后进行依次查找,如果下一个数不是上一个数+1得到的,那么上一个数+1就是我们要找的消失的数字。这题,按道理可以这么去写。

但是,观察各类常见的排序算法的时间复杂度详解图,最坏情况达不到我们该题要求的时间复杂度之内,在这里我们去运用排序,并不太合适。

各类排序时间复杂度对比
类别排序方法时间复杂度
平均情况最好情况最坏情况
插入排序直接插入O(n²)O(n)O(n²)
希尔排序O(n¹·³)O(n)O(n²)
选择排序直接排序O(n²)O(n²)O(n²)
堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)
交换排序冒泡排序O(n²)O(n)O(n²)
快速排序O(nlog₂n)O(nlog₂n)O(n²)
归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)
基数排序O(d(r+n))O(d(n+rd))O(d(r+n))
注:基数排序的复杂度中,r代表关键字的基数,d代表长度,n代表关键字的个数

 接下来,我们寻找其他方法击破此题。

思想2:异或运算

我们利用异或运算的规则(相同为0,相异为1),我可以先让一个变量x,初始值为0,与数组nums中numSize个元素进行异或运算,最后再与0 ~ numSize循环遍历的值进行异或,就能够得到是一个落单的数字,也就是我们最后要找的“消失的数字

代码实现: 

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

思想3:等差数列求和相减

我们可以写一个循环计算0~numSize所有数字之和,0到numSize个数字本质也是一个等差数列,也可以使用等差数列求和公式,得出一个sum1值。继续求出nums数组中所有整数之和,得出一个sum2值。sum1减去sum2得到的数字就是“消失的数字

代码实现: 

int missingNumber(int* nums, int numsSize){int i = 0;int sum1 = (1 + numsSize)*numsSize / 2;int sum2 = 0;for(i = 0;i < numsSize;i++){sum2 += nums[i];}return sum1 - sum2;
}


🤗🤗 好啦,本篇文章的创作就到此为止啦,如有不当,还请私信我纠正哦~

相关文章:

【Leetcode】消失的数字 [C语言实现]

&#x1f47b;内容专栏&#xff1a;《Leetcode刷题专栏》 &#x1f428;本文概括&#xff1a; 面试17.04.消失的数字 &#x1f43c;本文作者&#xff1a;花 碟 &#x1f438;发布时间&#xff1a;2023.4.10 目录 思想1&#xff1a;先排序再查找 思想2&#xff1a;异或运算 代…...

SpringBoot接口 - 如何实现接口限流之单实例

在以SpringBoot开发Restful接口时&#xff0c;当流量超过服务极限能力时&#xff0c;系统可能会出现卡死、崩溃的情况&#xff0c;所以就有了降级和限流。在接口层如何做限流呢&#xff1f; 本文主要回顾限流的知识点&#xff0c;并实践单实例限流的一种思路。 SpringBoot接口 …...

【花雕学AI】深度挖掘ChatGPT角色扮演的一个案例—CHARACTER play : 莎士比亚

CHARACTER play : 莎士比亚 : 52岁&#xff0c;男性&#xff0c;剧作家&#xff0c;诗人&#xff0c;喜欢文学&#xff0c;戏剧&#xff0c;爱情 : 1、问他为什么写《罗密欧与朱丽叶》 AI: 你好&#xff0c;我是莎士比亚&#xff0c;一位英国的剧作家和诗人。我很高兴你对我的…...

腾讯云物联网开发平台 LoRaWAN 透传接入 更新版

前言 之前有一篇文章介绍LoRaWAN透传数据&#xff0c;不过还是用物模型云端数据解析脚本&#xff0c;不是真正的透传。腾讯云物联网开发平台也支持对LoRaWAN原始数据的透传、转发。今天来介绍下。腾讯云 IoT Explorer 是腾讯云主推的一站式物联网开发平台&#xff0c;IoT 小能手…...

4.6--计算机网络之TCP篇之TCP的基本认识--(复习+深入)---好好沉淀,加油呀

1.TCP 头格式有哪些&#xff1f; 序列号&#xff1a; 在建立连接时由计算机生成的随机数作为其初始值&#xff0c;通过 SYN 包传给接收端主机&#xff0c;每发送一次数据&#xff0c;就「累加」一次该「数据字节数」的大小。 用来解决网络包乱序问题。 确认应答号&#xff1a; …...

一文吃透Elasticsearch

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址 如果访问不了Github&#xff0c…...

CPU占用率高怎么办?正确解决方法在这里!

案例&#xff1a;CPU占用率高怎么解决 【各位朋友&#xff0c;我的电脑现在运行太慢了&#xff0c;同事说可能是CPU占用率太高了&#xff0c;但对本电脑小白来说&#xff0c;完全不知道怎么处理&#xff0c;大家有什么好的方法可以解决这个问题吗&#xff1f;】 在计算机中&a…...

ChatGPT实现用C语言写一个学生成绩管理系统

随着ChatGPT爆火&#xff0c;大家都在使用ChatGPT来帮助自己提高效率&#xff0c;对于程序员来说使用它来写代码怎么样呢&#xff1f;今天尝试让ChatGPT&#xff0c;写了一个学生成绩管理系统。 问题是&#xff1a;使用C语言写一个学生成绩管理系统&#xff0c;要求使用链表&a…...

Swagger文档注释

本文以DRF框架为例使用 为什么要接口文档注释 一. 方便后端调试与后续接口更新&#xff1b; 二. 对于大型前后端分离项目&#xff0c;前后端人员是分开开发的&#xff0c;甚至前端的人你都不知道远在何处&#xff0c;这时候接口文档的重要性就太重要了。 三. 接口注释文档常用…...

pdf怎么转换ppt格式,两个方法转换

PDF作为一种常用的文件格式&#xff0c;被大众所熟悉。虽然PDF具备的稳定性&#xff0c;安全性&#xff0c;以及很强的兼容性可以让我们更方便顺畅的阅读PDF文件&#xff0c;但若是有需要展示PDF文件内容的时候&#xff0c;其优点就没有那么凸显了&#xff0c;这时还是将pdf转换…...

深度学习编译器相关的优秀论文合集-附下载地址

公司排名不分先后 目前在AI芯片编译器领域&#xff0c;有很多大公司在进行研究和开发。以下是一些主要的公司和它们在该领域的研究时间&#xff1a; 英伟达&#xff08;NVIDIA&#xff09;&#xff1a;英伟达是一家全球知名的图形处理器制造商&#xff0c;其在AI芯片编译器领域…...

vue全局使用svg

1、安装依赖 npm install svg-sprite-loader2、配置选项 在vue.config.js的chainWebpack里配置下面代码 解释&#xff1a;config.module.rule是一个方法&#xff0c;用来获取某个对象的规则。.exclude.add&#xff08;文件a&#xff09;是往禁用组添加文件a&#xff0c;就是对文…...

每天一点C++——杂记

结构体的深拷贝和浅拷贝 浅拷贝就是只拷贝指针&#xff0c;并不拷贝指针所指向的内容&#xff0c;深拷贝则会对指针的内容进行拷贝。浅拷贝会在一些场景下出现问题&#xff0c;看下面的例子&#xff1a; struct s {char * name;int age; };如果我定义 一个对象s1&#xff0c;…...

Document Imaging SDK 11.6 for .NET Crack

Document Imaging SDK for .NET View, Convert, Annotate, Process,Edit, Scan, OCR, Print 基本上被认为是一种导出 PDF 解决方案&#xff0c;能够为用户和开发人员提供完整且创新的 PDF 文档处理属性。它具有提供简单集成的能力&#xff0c;可用于增强用户 .NET 的文档成像程…...

数据挖掘(3.1)--频繁项集挖掘方法

目录 1.Apriori算法 Apriori性质 伪代码 apriori算法 apriori-gen(Lk-1)【候选集产生】 has_infrequent_subset(c,Lx-1)【判断候选集元素】 例题 求频繁项集&#xff1a; 对于频繁项集L{B,C,E}&#xff0c;可以得到哪些关联规则&#xff1a; 2.FP-growth算法 FP-tre…...

2023年信息安全推荐证书

随着网络安全行业的不断升温&#xff0c;相关的认证数量也不断增加&#xff0c;对于在网络安全行业发展的人才来说&#xff0c;提升职业竞争力最有效的办法之一&#xff0c;就是取得权威认证。 那么如何从繁多的适合网络安全从业者的证书中选择含金量高、发展潜力大的证书&…...

基于ArcGIS、ENVI、InVEST、FRAGSTATS等多技术融合提升环境、生态、水文、土地、土壤、农业、大气等领域应用

【自选】 时间地点&#xff1a;2023年7月22日-28日【乌鲁木齐】时间地点&#xff1a;2023年8月12日-18日【福建泉州】 【六天实践教学、提供全部资料】 专题一、空间数据获取与制图 1.1 软件安装与应用讲解 1.2 空间数据介绍 1.3海量空间数据下载 1.4 ArcGIS软件快速入门…...

基于ZC序列的帧同步

Zadoff-Chu序列是一种特殊的序列&#xff0c;具有良好的自相关性和很低的互相关性&#xff0c;这种性能可以被用来产生同步信号&#xff0c;作为对时间和频率的相关运算在TD-LTE系统中&#xff0c;Zadoff-Chu(ZC)序列主要应用于上行RS序列生成、PRACH前导序列生成以及主同步信号…...

配置NFS服务器-debian

NFS(Network Files System)是网络文件系统的英文缩写&#xff0c;由Sun公司于1980年开发&#xff0c;用于在UNIX操作系统间实现磁盘文件共享。在Linux操作系统出现后&#xff0c;NFS被Linux继承&#xff0c;并成为文件服务的一种标准。 通过网络&#xff0c;NFS可以在不同文件…...

正点原子STEMWIN死机

在用正点原子STM32F4开发板&#xff0c;搭配对应的button历程时&#xff0c;发现运行一会&#xff0c;button都无法使用了&#xff0c;以为是emwin死机了&#xff0c;但是看到Led还在闪烁&#xff0c;排除系统死机问题。那就是emwin的任务没有运行起来&#xff0c;但是打断点后…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...