C语言练习之消失的数字(两种解法)

2023-04-28 09:27:05 浏览数 (1)

前言

题目描述:

数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在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语言解决消失的数字这个题的思路。

这个题是我在做题时遇到的一道觉得很有意思的题,对我的做题思路有很大的启发作用,所以将它分享给大家。

如果本篇文章对你有所启发的话,希望可以支持支持作者,后续作者也会定期更新学习记录。谢谢大家!

0 人点赞