(C语言版)力扣(LeetCode)面试题 17.04. 消失的数字5种解法

news/2024/2/28 11:12:53

在这里插入图片描述

消失的数字

  • 题目介绍
  • 第一种解法:按位异或
  • 第二种解法:公式运算
  • 第三种解法:临时数组
  • 第四种解法:相加再相减
  • 第五种解法:快排加二分查找
  • 结语

题目介绍

该题目取自力扣(LeetCode)面试题 17.04. 消失的数字
链接:消失的数字
该题目主要考察时间复杂度的把握,题目如下:
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
注意:本题相对书上原题稍作改动
示例 1:
输入:[3,0,1]
输出:2
示例 2:
输入:[9,6,4,2,3,5,7,0,1]
输出:8
提示1:
你需要多长时间才能算出缺失数字的最小有效位?
提示2:
要找到缺失的数字中的最小有效位,你其实知道有多少个 0 和 1。例如,如果你看到最小有效位有 3 个 0 和 3 个 1,那么缺失的数字的最小值必定是 1。想想看:在任何 0 和 1 的序列中,你会得到 0,然后是 1,然后又是 0,然后又是 1,以此类推。
提示3:
一旦确定最小有效位是 0(或 1),就可以排除所有不以 0 作为最小有效位的数。这个问题和前面的有什么不同?

第一种解法:按位异或

这个解法我们先看一张图:
在这里插入图片描述
这种算法的思路主要是先设临时变量x=0,让它与nums数组中的数遍历按位异或,
此时x保存按位异或的值,再与0-n按位异或,最后得到的值就是缺的那个数字。
代码如下:

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

这里主要是利用了按位异或的特性,任何数与他本身按位异或得到的就是0;
那么在这里x按位异或了本身缺失数字的数组nums,再按位异或0-n的数字,
最后剩下的自然就是缺失的数字了。
时间复杂度:O(n)
空间复杂度:O(1)

第二种解法:公式运算

在这里插入图片描述
我们可以先看一张图,我们知道0-n在数学当中是一个自然数数列,那么他的前n项和公式就可以简化为[n(n-1)d]/2,那么这里的思路就是利用数列的前n项和公式先计算出0-n的总和,再建立一个临时变量k,利用一个for循环将nums中的元素逐个相加,最后两数相减得到的自然就是消失的数了。
代码如下:

int missingNumber(int* nums, int numsSize){int misNum = (numsSize+1)*numsSize/2;int k=0;for(int j = 0; j < numsSize; j++)k+=nums[j];misNum = misNum-k;return misNum;
}

时间复杂度:O(n)
空间复杂度:O(1)

第三种解法:临时数组

在这里插入图片描述
这里的思路就是用空间换时间,首先我们建立一个临时数组temp,使用malloc函数进行动态内存分配,临时数组temp比初始数组要多一个元素位置,然后将每一个位置都赋值为-1(因为nums是0-n,只有负数不会重复,想给负多少都可以),再将nums中的元素利用for循环逐个找到temp中对应下标进行赋值,最后剩下的-1所对应的下标即为消失的数字,最后再用for循环遍历数组,找到值为-1的元素下标,返回下标即为消失的数字(别忘记把temp的空间释放,否则会造成内存泄露的问题)。
代码如下:

int missingNumber(int* nums, int numsSize)
{int* temp = (int*)malloc(sizeof(int) * (numsSize + 1));if (temp == NULL){perror("missingNumber::malloc");return 0;}int i = 0;for (i = 0; i < numsSize + 1; i++){*(temp+i) = -1;}for (i = 0; i < numsSize; i++){temp[*nums] = *nums;nums++;}for (i = 0; i < numsSize + 1; i++){if (*(temp + i) == -1){free(temp);temp == NULL;return i;}}return ;
}

时间复杂度:O(n)
空间复杂度:O(n)

第四种解法:相加再相减

这种方法和公式法类似,这个的好处在于不用怎么动脑子,简单粗暴,先设立临时变量misNum,让misNum和0-n的值逐个相加,再利用一个for循环对nums数组进行遍历相减,最后得到的misNum的值即为消失的数。
代码如下:

int missingNumber(int* nums, int numsSize){int misNum = 0;for(int j = 0; j < numsSize + 1; j++)misNum += j;for(int i = 0; i < numsSize; i++)misNum -= nums[i];return misNum;
}

时间复杂度:O(n)
空间复杂度:O(1)

第五种解法:快排加二分查找

这种方法需要学到后序的数据结构中快速排序的知识,如果尚未学习,可以只参照前面4种解法,后续我还会出单独的板块介绍各类排序。

快速排序使用了“分治法”和“递归”技巧,将一个数组分成两个子数组,其中一个子数组的所有元素都小于另一个子数组的所有元素,并按照同样的方式对这两个子数组进行排序。快速排序中的关键步骤是“Partition(划分)”函数,它选择一个pivot(枢轴),然后通过交换元素的方式,将数组分成两个部分。

在该代码的“Partition”函数中,我们选择第一个元素为枢轴(pivot),然后使用两个指针low和high,从数组的两端开始遍历数组,交换两个指针所指的元素,以保证左侧的元素小于pivot,右侧的元素大于pivot。最后,将枢轴元素放在正确的位置上。

在“QuickSort”函数中,我们使用“Partition”函数将数组划分为两个子数组,然后对这两个子数组递归地进行排序。

在“missingNumber”函数中,我们先对输入数组进行排序,然后使用二分查找的技巧来找到缺失的数字。具体来说,我们定义左侧指针为0,右侧指针为数组的长度,然后计算中间位置mid,如果mid处的元素等于mid,则说明缺失的数字在mid的右侧,我们将左指针移到mid的右侧,否则缺失的数字在mid的左侧,我们将右指针移到mid的左侧。最终,左侧指针指向的位置就是消失的数字。
代码如下:

 int Partition(int *A, int low, int high){int pivot=A[low];while(low<high){while(low<high && A[high]>=pivot) high--;A[low]=A[high];while(low<high && A[low]<=pivot) low++;A[high]=A[low];}A[low]=pivot;return low;}void QuickSort(int *A, int low, int high){if(low<high){int PartitionPos = Partition(A,low, high);QuickSort(A,low,PartitionPos-1);QuickSort(A,PartitionPos+1, high);}}int missingNumber(int* nums, int numsSize){QuickSort(nums, 0, numsSize-1);int left=0, right=numsSize;while(left<right){int mid=left+(right-left)/2;if(nums[mid]==mid){left=mid+1;}else{right=mid;}}return left;}

时间复杂度:O(nlogn)
空间复杂度:O(1)

需要注意的是,这个题目在不考虑时间复杂度的情况下,可以使用别的排序方法,比如,冒泡排序,但是它的时间复杂度为O(n*2),因此不符合本题题意,不过有兴趣的小伙伴可以试一试。

结语

在后续更新中,我会一直写关于OJ题的题解,有兴趣的小伙伴可以关注作者,和作者讨论其他OJ题目,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!
在这里插入图片描述


http://www.ppmy.cn/news/42232.html

相关文章

W80X|联盛德|nulllab空想实验室|Arduino适配|学习(6):w80x_arduino环境安装

文章目录概述官方推荐安装方法&#xff08;实测未成功&#xff09;readme中的安装步骤&#xff1a;手动安装方法&#xff1a;clone项目至本地手动新建w80x_arduino管理器存放目录w80x_arduino开发进展说明概述 此开源项目由nulllab空想实验室团队维护&#xff0c;并得到联盛德…

尚硅谷大数据技术Hadoop教程-笔记04【Hadoop-MapReduce】

视频地址&#xff1a;尚硅谷大数据Hadoop教程&#xff08;Hadoop 3.x安装搭建到集群调优&#xff09; 尚硅谷大数据技术Hadoop教程-笔记01【大数据概论】尚硅谷大数据技术Hadoop教程-笔记02【Hadoop-入门】尚硅谷大数据技术Hadoop教程-笔记03【Hadoop-HDFS】尚硅谷大数据技术Ha…

static关键字的作用

通常情况下成员变量隶属于对象层级&#xff0c;每创建一个对象就需要申请独立的内存空间来存放该对象独立的成员变量信息&#xff0c;若所有对象的某个成员变量数值完全一样却又单独存放会造成内存空间的浪费。 为了解决上述问题&#xff0c;则使用static关键字修饰成员变量表…

Unity ads广告插件的使用

介绍 Unity Ads SDK 由领先的移动游戏引擎创建,无论您在 Unity、Xcode 还是 Android Studio 中进行开发,都能为您的游戏提供全面的货币化框架。 使用 Unity Ads 将各种广告格式合并到游戏中的自然呈现点中。例如,您可以实施激励视频广告来构建更强大的游戏经济,同时为您的…

VVC之编码结构

VVC之编码结构&#xff08;新一代通用视频编码的读书笔记&#xff09;缩写概述EncAppmain函数解读缩写 缩写含义CVSCoded Video Sequence, 编码视频序列IRAPIntra Random Access Point, 帧内随机接入点GDRGradual Decoding Refresh, 逐渐解码刷新AUAccess Unit, 访问单元PUPic…

【Matlab算法】粒子群算法求解二维线性优化问题(附MATLAB代码)

MATLAB求解二维线性优化问题前言正文函数实现可视化结果前言 二维线性优化问题指的是在二维空间中&#xff0c;对于一个由线性函数构成的目标函数&#xff0c;通过限制自变量的范围或满足特定的约束条件&#xff0c;寻找一个最优解&#xff08;最小值或最大值&#xff09;。这…

C语言从入门到精通第2天(深度解析C语言数据类型及取值范围)

C语言基本数据类型及取值范围数据存储概述基本数据类型整型数的二进制表示浮点型数的二进制表示取值范围数据存储概述 C语言的变量有着不同的数据类型&#xff0c;每种数据类型的取值空间都是不同的&#xff0c;因此&#xff0c;不同数据类型的变量&#xff0c;其取值空间也不…

Centos7安装部署Jenkins

Jenkins简介&#xff1a; Jenkins只是一个平台&#xff0c;真正运作的都是插件。这就是jenkins流行的原因&#xff0c;因为jenkins什么插件都有 Hudson是Jenkins的前身&#xff0c;是基于Java开发的一种持续集成工具&#xff0c;用于监控程序重复的工作&#xff0c;Hudson后来被…

在 Linux 上使用 Pigz 更快地压缩文件,真的快!

Pigz是一款快速压缩文件的工具&#xff0c;它能够使用多个CPU核心进行压缩&#xff0c;使得压缩速度得到了极大的提升。在本文中&#xff0c;我们将介绍如何在Linux上使用Pigz来更快地压缩文件。 安装Pigz 在开始使用Pigz之前&#xff0c;我们需要先安装它。在大多数Linux发行…

【ros2】ubuntu18.04同时安装ros1和ros2

序言 ubuntu18.04&#xff08;已安装ros melodic&#xff09;中安装ros2 dashing版本&#xff0c;以支持ros2工程的编译使用 1. 安装ros melodic 参考我之前的文章&#xff1a;docker容器中安装melodic-ros-core过程总结 2. 安装ros2 dashing &#xff08;1&#xff09;设置…

[论文速览] Sparks of Artificial General Intelligence: Early experiments with GPT-4

Sparks of Artificial General Intelligence: Early experiments with GPT-4 2023.3.22 微软官方发布了目前人类史上最强AI模型 GPT-4 的综合能力评估论文&#xff0c;总所周知&#xff0c;2023年是通用人工智能&#xff08;Artificial General Intelligence&#xff0c;AGI&a…

Amazon SageMaker简直就是机器学习平台的天花板

一、前言 最近参与了亚马逊云科技【云上探索实验】活动&#xff0c;通过Amazon SageMaker基于Stable Diffusion模型&#xff0c;非常简单快速搭建的第一个AIGC&#xff0c;一开始以为非常复杂&#xff0c;不懂动手操作&#xff0c;但实际上操作非常简单&#xff0c;没有想象中…

day22—选择题

文章目录1.下列数据结构具有记忆功能的是&#xff08;C&#xff09;2.循环队列放在一维数组A[0…M-1]中&#xff0c;end1指向队头元素&#xff0c;end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作&#xff0c;队列中最多能容纳M-1个元素。初始时为空&#x…

Python数据结构与算法-树

一、树的概念详情见 https://blog.csdn.net/little_limin/article/details/129845592 Python数据结构与算法-堆排序&#xff08;NB组&#xff09;—— 一、树的基础知识二、树的实例&#xff1a;模拟文件系统1、树的存储树结构也是链式存储的&#xff0c;与链表的结构相似&…

【ChatGPT】AI发展如此火热,程序员的发展呢?

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; 目录一、AI已来&#xff0c;ChatGPT你用上了吗&#x1f33e;二、AI之路&#xff0c;这是社会在发展&#x1f331;三、AI时代&#xff0c;程序员应该怎么做&#x1f334;一、AI已来&#xff0c;ChatGPT你用上了吗&…

(五)【软件设计师】计算机系统—进制习题

文章目录一、2010下半年第4题二、2012上半年第2题三、2013上半年第5、6题四、2014上半年第6题五、2014下半年第4题六、2015下半年第5题七、2016上半年第5题八、2017下半年第3题九、2019下半年第4、5题一、2010下半年第4题 设用2K4位的存储器芯片组成16K8位的存储器&#xff08;…

d2l Markov序列模型

本节的任务是使用Markov模型对后续序列进行预测&#xff0c;使用sin函数&#xff0b;噪声绘制1000个样本点&#xff0c;取tau为4&#xff0c;即利用后四个的信息预测第五个。 目录 1.构造样本点 2.抽取iter 3.构造网络 4.训练 5.预测 5.1单步 5.1多步 1.构造样本点 T …

【SQL Server】数据库开发指南(二)MSSQL数据库开发对于库、表、数据类型、约束等相关操作

文章目录一、SQL Server 中的 GO 关键字二、切换不同数据库三、创建、删除数据库3.1 创建方式1&#xff1a;基本创建&#xff08;适合演示和学习&#xff09;3.2 创建方式2&#xff1a;设置存储位置以及大小等3.2 创建方式3&#xff1a;同时设置主与次数据文件信息五、SQL Serv…

测试开发备战秋招面试3

努力了那么多年,回头一望,几乎全是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦虑和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧&#xff01; 目录 1.讲一下redis和mySQL的区别&#xff1f; 2.讲一下…

Python高级编程 type、object、class的区别 python中常见的内置类型 魔法函数

python中一切皆对象 代码块&#xff1a; a 1 print(type(a)) print(type(int))控制台输出&#xff1a; <class int> <class type>也就是说在python中int类是由type类生成的&#xff0c;而数字1是由int类生成的。 代码块&#xff1a; b "abc" prin…
最新文章