网站建设申请费用,建筑设计学什么的,湛江seo推广外包,网络综合设计实验报告#x1f47b;内容专栏#xff1a;《Leetcode刷题专栏》 #x1f428;本文概括#xff1a; 面试17.04.消失的数字 #x1f43c;本文作者#xff1a;花 碟 #x1f438;发布时间#xff1a;2023.4.10 目录
思想1#xff1a;先排序再查找
思想2#xff1a;异或运算
代… 内容专栏《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(rn))O(d(nrd))O(d(rn))注基数排序的复杂度中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;
} 好啦本篇文章的创作就到此为止啦如有不当还请私信我纠正哦~
