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

👻内容专栏:《Leetcode刷题专栏》
🐨本文概括: 面试17.04.消失的数字
🐼本文作者:花 碟
🐸发布时间:2023.4.10
目录
思想1:先排序再查找
思想2:异或运算
代码实现:
思想3:等差数列求和相减
代码实现:
点击跳转到Leetcode的OJ平台 17.04 消失的数字
题目:
数组
nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在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语言实现]
👻内容专栏:《Leetcode刷题专栏》 🐨本文概括: 面试17.04.消失的数字 🐼本文作者:花 碟 🐸发布时间:2023.4.10 目录 思想1:先排序再查找 思想2:异或运算 代…...
SpringBoot接口 - 如何实现接口限流之单实例
在以SpringBoot开发Restful接口时,当流量超过服务极限能力时,系统可能会出现卡死、崩溃的情况,所以就有了降级和限流。在接口层如何做限流呢? 本文主要回顾限流的知识点,并实践单实例限流的一种思路。 SpringBoot接口 …...
【花雕学AI】深度挖掘ChatGPT角色扮演的一个案例—CHARACTER play : 莎士比亚
CHARACTER play : 莎士比亚 : 52岁,男性,剧作家,诗人,喜欢文学,戏剧,爱情 : 1、问他为什么写《罗密欧与朱丽叶》 AI: 你好,我是莎士比亚,一位英国的剧作家和诗人。我很高兴你对我的…...
腾讯云物联网开发平台 LoRaWAN 透传接入 更新版
前言 之前有一篇文章介绍LoRaWAN透传数据,不过还是用物模型云端数据解析脚本,不是真正的透传。腾讯云物联网开发平台也支持对LoRaWAN原始数据的透传、转发。今天来介绍下。腾讯云 IoT Explorer 是腾讯云主推的一站式物联网开发平台,IoT 小能手…...
4.6--计算机网络之TCP篇之TCP的基本认识--(复习+深入)---好好沉淀,加油呀
1.TCP 头格式有哪些? 序列号: 在建立连接时由计算机生成的随机数作为其初始值,通过 SYN 包传给接收端主机,每发送一次数据,就「累加」一次该「数据字节数」的大小。 用来解决网络包乱序问题。 确认应答号: …...
一文吃透Elasticsearch
本文已经收录到Github仓库,该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点,欢迎star~ Github地址 如果访问不了Github,…...
CPU占用率高怎么办?正确解决方法在这里!
案例:CPU占用率高怎么解决 【各位朋友,我的电脑现在运行太慢了,同事说可能是CPU占用率太高了,但对本电脑小白来说,完全不知道怎么处理,大家有什么好的方法可以解决这个问题吗?】 在计算机中&a…...
ChatGPT实现用C语言写一个学生成绩管理系统
随着ChatGPT爆火,大家都在使用ChatGPT来帮助自己提高效率,对于程序员来说使用它来写代码怎么样呢?今天尝试让ChatGPT,写了一个学生成绩管理系统。 问题是:使用C语言写一个学生成绩管理系统,要求使用链表&a…...
Swagger文档注释
本文以DRF框架为例使用 为什么要接口文档注释 一. 方便后端调试与后续接口更新; 二. 对于大型前后端分离项目,前后端人员是分开开发的,甚至前端的人你都不知道远在何处,这时候接口文档的重要性就太重要了。 三. 接口注释文档常用…...
pdf怎么转换ppt格式,两个方法转换
PDF作为一种常用的文件格式,被大众所熟悉。虽然PDF具备的稳定性,安全性,以及很强的兼容性可以让我们更方便顺畅的阅读PDF文件,但若是有需要展示PDF文件内容的时候,其优点就没有那么凸显了,这时还是将pdf转换…...
深度学习编译器相关的优秀论文合集-附下载地址
公司排名不分先后 目前在AI芯片编译器领域,有很多大公司在进行研究和开发。以下是一些主要的公司和它们在该领域的研究时间: 英伟达(NVIDIA):英伟达是一家全球知名的图形处理器制造商,其在AI芯片编译器领域…...
vue全局使用svg
1、安装依赖 npm install svg-sprite-loader2、配置选项 在vue.config.js的chainWebpack里配置下面代码 解释:config.module.rule是一个方法,用来获取某个对象的规则。.exclude.add(文件a)是往禁用组添加文件a,就是对文…...
每天一点C++——杂记
结构体的深拷贝和浅拷贝 浅拷贝就是只拷贝指针,并不拷贝指针所指向的内容,深拷贝则会对指针的内容进行拷贝。浅拷贝会在一些场景下出现问题,看下面的例子: struct s {char * name;int age; };如果我定义 一个对象s1,…...
Document Imaging SDK 11.6 for .NET Crack
Document Imaging SDK for .NET View, Convert, Annotate, Process,Edit, Scan, OCR, Print 基本上被认为是一种导出 PDF 解决方案,能够为用户和开发人员提供完整且创新的 PDF 文档处理属性。它具有提供简单集成的能力,可用于增强用户 .NET 的文档成像程…...
数据挖掘(3.1)--频繁项集挖掘方法
目录 1.Apriori算法 Apriori性质 伪代码 apriori算法 apriori-gen(Lk-1)【候选集产生】 has_infrequent_subset(c,Lx-1)【判断候选集元素】 例题 求频繁项集: 对于频繁项集L{B,C,E},可以得到哪些关联规则: 2.FP-growth算法 FP-tre…...
2023年信息安全推荐证书
随着网络安全行业的不断升温,相关的认证数量也不断增加,对于在网络安全行业发展的人才来说,提升职业竞争力最有效的办法之一,就是取得权威认证。 那么如何从繁多的适合网络安全从业者的证书中选择含金量高、发展潜力大的证书&…...
基于ArcGIS、ENVI、InVEST、FRAGSTATS等多技术融合提升环境、生态、水文、土地、土壤、农业、大气等领域应用
【自选】 时间地点:2023年7月22日-28日【乌鲁木齐】时间地点:2023年8月12日-18日【福建泉州】 【六天实践教学、提供全部资料】 专题一、空间数据获取与制图 1.1 软件安装与应用讲解 1.2 空间数据介绍 1.3海量空间数据下载 1.4 ArcGIS软件快速入门…...
基于ZC序列的帧同步
Zadoff-Chu序列是一种特殊的序列,具有良好的自相关性和很低的互相关性,这种性能可以被用来产生同步信号,作为对时间和频率的相关运算在TD-LTE系统中,Zadoff-Chu(ZC)序列主要应用于上行RS序列生成、PRACH前导序列生成以及主同步信号…...
配置NFS服务器-debian
NFS(Network Files System)是网络文件系统的英文缩写,由Sun公司于1980年开发,用于在UNIX操作系统间实现磁盘文件共享。在Linux操作系统出现后,NFS被Linux继承,并成为文件服务的一种标准。 通过网络,NFS可以在不同文件…...
正点原子STEMWIN死机
在用正点原子STM32F4开发板,搭配对应的button历程时,发现运行一会,button都无法使用了,以为是emwin死机了,但是看到Led还在闪烁,排除系统死机问题。那就是emwin的任务没有运行起来,但是打断点后…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
