题目描述
数组 nums
包含从 0
到 n
的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在
O
(
n
)
O(n)
O(n) 时间内完成吗?
示例 1:
输入:[3,0,1]
输出:2
leetcode链接:消失的数字
⭕️ 思路1:
/*
思路1:开辟一个 n + 1 的空间,每个元素初始化为-1,遍历目标数组,把目标数组当前元素
当作新开辟数组的下标并存入当前元素。
最后遍历新开辟的数组,那个是-1的元素下标就是消失的数字
[3,0,1]
[-1 , -1 , -1 , -1]
0 1 2 3
[0 , 1 , -1 , 3]
result : 2
*/
int missingNumber(int* nums, int numsSize){
int * res = (int *)malloc(sizeof(int) * (numsSize + 1));
for (int i = 0; i < numsSize + 1; i++) {
res[i] = -1;
}
for (int i = 0; i < numsSize; i++) {
res[nums[i]] = nums[i];
}
for (int i = 0; i < numsSize + 1; i++) {
if (res[i] == -1) {
free(res);
return i;
}
}
free(res);
return 0;
}
第一种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( N ) O(N) O(N)。
⭕️ 思路2:
/*
思路2:异或的方式,给一个变量res与目标数组中的所有元素异或,在与0 - numsSize + 1所有元素异或
因为目标数组中少一个元素,所以最后res的值就保存的是消失的数字。
[3 , 0 , 1]
[0 , 1 , 2 , 3]
3 ^ 3 = 0 -> 0 ^ 0 = 0 -> 1 ^ 1= 0 -> 0 ^ 2 = 2
result: 2
*/
int missingNumber(int* nums, int numsSize){
int res = 0;
for (int i = 0; i < numsSize; i++) {
res ^= nums[i];
}
for (int i = 0; i < numsSize + 1; i++) {
res ^= i;
}
return res;
}
第二种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( 1 ) O(1) O(1)。
⭕️ 思路3:
/*
思路3:等差数列求和公式 ((首项+尾项)*项数) / 2,用0 - n之间的求和结果减去目标数组的
每一个元素即可得到消失的数字
*/
int missingNumber(int* nums, int numsSize){
int resSum = ((0 + numsSize) * (numsSize + 1)) / 2;
int sum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
}
return resSum - sum;
}
第三种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( 1 ) O(1) O(1)。文章来源:https://www.toymoban.com/news/detail-511070.html
文章来源地址https://www.toymoban.com/news/detail-511070.html
到了这里,关于leetcode消失的数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!