C语言练习之消失的数字（两种解法）

摘星

发布于 2023-04-28 09:27:05

3320

发布于 2023-04-28 09:27:05

文章被收录于专栏：C/C++学习

前言

题目描述：

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

测试举例：

输入：[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

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

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;
}