前言
题目描述:
数组nums
包含从0
到n
的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
测试举例:
代码语言:javascript复制输入:[3,0,1]
输出:2
一、思路
思路一(异或法)
首先要明白什么是异或(异或就是二进制位的数值,相等则为0,不相等则为1)
假设a!=b,则有以下公式:
a^a = 0;
a^b = b^a;
0^a = a;
根据公式可以想到:
先将0~n的所有数字全部异或
ret1 = 0^1^……^n;
再将数组(缺失数字)中的数全部异或
ret2 = nums[0]^nums[2]^……^nums[numsSize-1];
最后将ret1和ret2异或,所得结果就是缺失的数字。
思路二(求和法)
由观察可知,缺少的数字等于0~n数字之和减去0~n除了所缺少数字外其他数字之和。
二、代码
为了方便大家的交流和学习,我将函数的代码放置在下方。
代码1
代码语言:javascript复制int missingNumber(int* nums, int numsSize){
int i = 0;
int sum1 = 0,sum2 = 0;
for(i = 0;i < numsSize 1; i )//0~n个整数之和
{
sum1 = i;
}
for(i = 0; i < numsSize ;i )//所给数组的元素之和
{
sum2 = nums[i];
}
return sum1 - sum2;
}
代码2
代码语言:javascript复制int missingNumber(int* nums, int numsSize){
int i = 0;
int ret1 = 0,ret2 = 0;
for(i = 0;i < numsSize 1; i )//0~n所有整数的异或
{
ret1 ^= i;
}
for(i = 0; i < numsSize ;i )//所给数组的所有元素的异或
{
ret2 ^= nums[i];
}
return ret1^ret2;
}
总结
以上就是今天要讲的内容,本文简单的介绍了如何用C语言解决消失的数字这个题的思路。
这个题是我在做题时遇到的一道觉得很有意思的题,对我的做题思路有很大的启发作用,所以将它分享给大家。
如果本篇文章对你有所启发的话,希望可以支持支持作者,后续作者也会定期更新学习记录。谢谢大家!