当前位置：首页 > article >正文

面试题-消失的数字-异或

article 2025/2/3 23:05:35

消失的数字

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

int missingNumber(int* nums, int numsSize) {}

分析

本题对时间复杂度的要求是O(n)。
利用异或相同为0，不同为1；也就是相同的数异或为0；任何数异或0，结果为原来的数。
思路1：单身狗思想：将数组中所有数异或起来的值，再与0~numsSize之间的值异或，最后的结果就是没出现过的数。

注：
异或符合交换律和结合律
1 ^ 1 ^ 3 = 3
1 ^ 3 ^ 1 = 3

思路2：公式法：0~numsSize的和减数组元素的和，结果就是没出现过的数。

代码

代码1

int missingNumber(int* nums, int numsSize) 
{
    int val = 0;
    for(int i=0; i<numsSize; i++)
    {
        val ^= nums[i];
    }
    for(int i=0; i<=numsSize; i++)
    {
        val ^= i;
    }
    return val;
}

代码解释：
因为任何数异或0为原数，所以使用val=0为原始值。
又因为异或符合交换律和结合律，所以
val=0 ^ ( 0 ^ 1 ^ 3 ) ^ ( 0 ^ 1 ^ 2 ^ 3 ) = 2

代码2：

int missingNumber(int* nums, int numsSize) 
{
    int sum = numsSize*(numsSize+1)/2;
    for(int i=0; i<numsSize; i++)
    {
        sum -= nums[i];
    }
    return sum;
}