脚本宝典收集整理的这篇文章主要介绍了leetcode刷题之消失的数字(超详解刷爆力扣),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
大家好啊,我是小生啊🙈🙈🙈 从今天开始小生将会和大家一起刷题,从今天开始小生也会开辟新的专栏。😜😜😜
🌞🌞🌞 让我们每日练习,刷爆力扣,冲冲冲
兄弟们,废话不多说直接看题:🙉🙉🙊
示例1: 输入:[3,0,1] 输出:2 示例2: 输入:[9,6,4,2,3,5,7,0,1] 输出:8
由图片分析可得,该题目对算法由一定的要求,首先我们得明白@R_250_1304@为O(N)算法意味着什么。我们先来看看算法的时间复杂度对比图,在大概了解到题目所需要的算法优化程度后,我们就可以着手来做题目啦😎😎😎
既然是0~n内的整数,且仅仅缺少了一个整数,那么我们就可以先对该数组进行排序,再检验相邻下标的元素是否相差为1,理论上便可以得出最后的结果。 在这里小生不得不提醒大家,排序的复杂度是相当高的,即便是最复杂度最小的快排,在这个程序内也不合适。我们可以通过图片来认识😯😯😯
由该表可知,当我们使用效率最高的排序且考虑最坏的情况时,复杂度为N*LOG2(N),显然在这个题目中超出了复杂度的要求,因此,这种思路虽然是最直接的但是一定会超时。别慌,我们再想想其他办法。
具体问题具体分析,既然我们该数组存储的是0~n里面的整数且只缺少了一个整数,那我们可以用将0 ~ n所有的整数相加,再把该数组中的整数相加最后两个和向减即可。💪💪💪
但是我们可以举一反三,如果题目更改一下,缺失的并非一个数字而是多个数字呢?那这种方法是不是就不起作用啦?这种方法还是不错的,那有没有更加普适性的方法呢?大家可以思考一下
位与位异或,相同为0,不相同为1.同时,因为异或是位与位进行计算的,所以异或的顺序不重要,结果是一样的,由此,在我们这个题目中,我们可以通过一下思路实现: 因为异或相同得零,不同得1,所以使用一个变量将数组中所有元素异或,然后再和1到n进行异或,得到的就是消失的数字😎😎😎
定义两个变量,一个通过循环存储数组所有元素的和,一个通过循环存储1~n所有数字的和,最后相减即可。 代码如下👇👇👇👇
int Missingnum(int* nums, int numsSize)
{
int sum1 = 0;
int sum2 = 0;
//求出数组所有元素之和
for (int i = 0; i < numsSize; i++)
{
sum1 += nums[i];
}
//求出1~n所有元素之和
for (int i = 0; i < numsSize + 1; i++)
{
sum2 += i;
}
return sum2 - sum1;
}
定义一个初始化为0的变量,依次与该数组和1~n的每一个数字异或,最后留下来的便是所求的数字了 直接看代码👇👇👇👇
int Missingnum(int* nums, int numsSize)
{
int tmp = 0;
//依次与数组的每一个元素异或
for (int i = 0; i < numsSize; i++)
{
tmp ^= nums[i];
}
//依次与1~n个数字异或
for (int i = 0; i < numsSize +1; i++)
{
tmp ^= i;
}
return tmp;
}
以上是脚本宝典为你收集整理的leetcode刷题之消失的数字(超详解刷爆力扣)全部内容,希望文章能够帮你解决leetcode刷题之消失的数字(超详解刷爆力扣)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。