提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。 示例 1:
输入:nums = [3,0,1] 输出:2 解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2
是丢失的数字,因为它没有出现在 nums 中。
示例 2:输入:nums = [0,1] 输出:2 解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2
是丢失的数字,因为它没有出现在 nums 中。
示例 3:输入:nums = [9,6,4,2,3,5,7,0,1] 输出:8 解释:n = 9,因为有 9 个数字,所以所有的数字都在范围
[0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。
示例 4:输入:nums = [0] 输出:1 解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1
是丢失的数字,因为它没有出现在 nums 中。
题目已经清楚的说明了,要我们找到[ 0 n]中数组每出现的数字
解法1
大家看到题的时候的第一想法就是循环嵌套吧,通过遍历来找到那个数字。
好,那么我们就来实现一下
int missingNumber(int* nums, int numsSize) {
for (int i = 0; i <= numsSize; i++) {//第一个循环,将[1~n]的数字遍历一次
int t=0;//标志变量
for (int j =0 ; j < numsSize; j++) {//在数组中寻找i找不到就是的话就是丢失的数字
if (nums[j] == i)
{
t = 1;//找到i就是t=1加打破
break;
}
}
if (t == 0)
return i;//返回丢失的数字
}
}
优点:这种解法简单,只需要循环嵌套即可
缺点:时间复杂度O(n*n),时间过长可能超过时限
解法2
我们要注意一个点就是这些数字是[ 0 n]且数组数字不重复,那么我们可以将0~n都加起来然后再减去数组中的所有数字,得到的就是丢失的数字了
实现:
int missingNumber(int* nums, int numsSize) {
int r=0;
for(int i=1;i<=numsSize;i++)//将0-n的数字都加起来
r=r+i;
for(int i=0;i<numsSize;i++)
r=r-nums[i];减去数组中所有的数字
return r;
}
这种解法很好,时间复杂度在O(n),也很容易实现
解法3
第三种方法就是利用异或了
异或有两个性质
1.0和任何一个数异或都等于那个数
2.相同的数字异或的结果为0
我们可以设置一个数为0,再和[0-n]的数字异或,之后再和数组的各个元素异或,这样一来相同的数字就被抵消了,剩下0和丢失的那个数,又因为0和任何一个数异或都等于那个数,所以最后得到的数就是丢失的数字了
实现:
int missingNumber(int* nums, int numsSize) {
int r = 0;
for (int i = 1; i <= numsSize; i++)//让r和0-n的数字都异或
r = r ^ i;
for (int i = 0; i < numsSize; i++)//再和数组中的所有元素异或,最终就是丢失的数字了
r = r ^ nums[i];
return r;
这种解法很好,就是有点难想到,时间复杂度为O(n)
总结
相比于第一种后面的两种在时间上有优势,但是后面两种有点难想到,特别是第三种文章来源:https://www.toymoban.com/news/detail-758843.html
今天的分享就到这里了,谢谢大家的观看文章来源地址https://www.toymoban.com/news/detail-758843.html
到了这里,关于力扣--268丢失的数字(三种解法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!