一、题目描述
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
示例 1:
输入:[3,0,1]
输出:2
示例 2:
输入:[9,6,4,2,3,5,7,0,1]
输出:8
- 本题的题目思路很简单,就是给你一个数组,然后让你输出连续的数组中消失的那一个数字。本题我给出两种解法
二、方法1:求和相减【C语言】
1、思路分析
首先我们来看看使用求和相减法的思路是怎样的
- 这个思路不难想到,只需要运用一个等差数列的求和公式求和从0到n的总和,然后用这个总和值减去题目给出的数组数字的总和,无论应对哪一个案例,这个方法都是适用的
2、整体代码展示
我们来看一下代码
int missingNumber(int* nums, int numsSize){
//1.先使用等差数列求和公式求出总的和
int ret = (1 + numsSize) * numsSize/ 2;
//2.使用循环遍历这个数组,题目给出的所有输出
for(int i = 0;i < numsSize; ++i)
//3.实行一个作差,找出缺少的那一个数
ret -= nums[i];
//4.返回的结果就是缺失的那个数字
return ret;
}
3、代码详解
然后我们分步来讲解一下
- 首先第一步,使用一个等差数列的求和公式,求出从1到numSize所有数字的总和,放入变量ret中
- 然后第二步,使用循环遍历一下整个数组,用上面求出的ret减去题目给出的nums数组中的每一个数字
- 最后第三步,返回的结果即为消失的那个数组
可以看出,本思路非常简单,这个大家应该是都可以想到,接下去我们来看第二个思路
三、方法2:异或位运算【C语言】
1、思路分析
- 异或这种位运算,不知道大家之前在学习C语言的时候有没有注意,如果忘记了就再去看一下吧 -- >异或位运算
- 整体的思路大概是声明一个变量,将其初始化为0,然后和题目中给出的所有数字先以后一遍,接着再用异或完的数据与0~N的数字再进行一个异或,最后变量中保存的数字便是消失的那个数字
2、整体代码展示
先看一下整体的代码
int missingNumber(int* nums, int numsSize){
int N = numsSize;
int x = 0; //存储异或的数字
//1.首先对给出的所有数字进行一个异或
for(int i = 0;i < numsSize; ++i)
x ^= nums[i];
//2.再将给出的数字与完整的所有0~N的数进行一个异或
for(int j = 0;j <= N; ++j)
x ^= j;
//3.两次异或后的结果即为消失数字
return x;
}
3、代码详解
由于下面要用到异或的规则,所以先给出规则的定义
【所有数字和0异或都是它自己本身】
【所有数字和它自己异或都是0】
【异或运算具备交换律和结合律】
- 然后我们来分析一下这段代码以及解释一下这个异或的逻辑
- 从以上图示可以看出,首先第一步,将变量x与题目给出是所有数进行一个异或
- 然后第二步,再与从0~N的所有数字进行一个异或后,因为异或运算具有交换律和结合律,所以两两相同的数字异或后一定为0,最后其实只剩下8和9这两个数字,然后再和9去进行一个异或,然后9和9先异或就是0,0再和8异或就是8自己本身
- 最后这个x的值就是8,返回即可
如果对以上逻辑有异或,可以到编译器里自己调试一下,就可以很清楚了
四、方法3:哈希表【C++】
1、思路分析
然后最后一种思路呢,是我近阶段才看到的一种方法,觉得可不错,也分享给大家,主要是使用到高阶数据结构中的【哈希表】
- 整体的思路大概是将题目中给出的数字先放入哈希表中,然后再去遍历从0~n的所有数字,去哈希表中寻找是否有与其相同的数字,若是在遍历的过程中发现有数字不存在,则说明这个就是消失的那个数字,记录下这个数字跳出循环的遍历,返回这个数字即可
2、整体代码展示
然后展示一下代码
class Solution {
public:
int missingNumber(vector<int>& nums) {
unordered_set<int> set;
int n = nums.size();
//1.首先讲题目给出的数字放入哈希表中
for(int i = 0;i < n; ++i)
set.insert(nums[i]);
int missing = -1; //消失的数字
//2.然后遍历从0~n的所有数字,去哈希表中寻找是否有与其相同的数字
for(int j = 0;j <= n; ++j)
{
//3.若是发现有数字没有在表中,则表明此为消失的数字
if(!set.count(j))
{
//4.记录这个消失的数字
missing = j;
break; //已经找到这个数字,跳出循环的遍历
}
}
return missing;
}
};
3、代码详解
然后我们对代码来解说一下,逻辑并不复杂,一步步下来就行
- 首先呢我们需要去定义一个哈希集合,用来存放题目中给出的数字
- 接着就是将题目中给出的所有数字放入哈希集合中集合,这里使用的是一个API【insert()】
- 其次我们要定义一个变量用于保存那个消失的数字,然后遍历从0~n的所有数字,去哈希表中寻找是否有与其相同的数字。这里使用的是一个API【count()】,作用是统计当前的这个数字是否又在哈希表中出现过,取反【!】表示的就是没有出现的数字,若是符合,则使用missing变量去记录这个数字,然后break跳出循环,因为已经找到了和这个消失的数字就不要再寻找了
- 最后返回即可
不过对于哈希表来说,虽然是可以AC,但是呢由于哈希表需要维护数组,因此空间复杂度为O(N),不过题目要求在O(N)的时间复杂度内完成,哈希表起到的其实就是一个空间换时间的操作,对于时间的话在搜索算法中可以当仁不让的O(1)
五、总结与提炼
- 本文我们主要是讲解了一道面试题,叫做【消失的数字】,面对题目给出的数组,查找出中间消失的那个数字
- 在本文中,主要是给出了三种解法【求和相减】、【异或位运算】、【哈希表】,三种方法各有不同,分享出来希望你都可以掌握,多学会一种解法总是好的
以上就是本文的所有内容,如有问题请于评论区留言或者私信我,感谢您对本文的观看:hibiscus: