【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的任务没有运行起来,但是打断点后…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
