当前位置: 首页 > 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;但是打断点后…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...