每日一题：消失的数字

链接: 消失的数字

思路

• 使用排序
• 利用求和
• 利用异或

使用排序

因为题目说这个数组是从0到n的所有整数，所以首先大家想到的可能是将这个数组进行排序比如冒泡排序。 这个想法虽然不错，但是题目又要求是否可以在O(n) 时间复杂度完成，所以这里不推荐使用排序的方法。

利用求和

由于这个数组的一个特点：它是从0到n的所有整数组成的，只是缺了一个。 那就有了一个想法，就是先把0到n完整的相加在一起，减掉这个数组的和，就等于这个缺的这个数字了！，简单的说就是这样子：

0到n等差数列的和 - 数组所有数的和 = 消失的数字

代码语言：javascript复制

int missingNumber(int* nums, int numsSize){
    //等差数列的和
    int all = ((0   numsSize) * (numsSize   1)) / 2;

    //数组元素的和
    int sum = 0;
    for(int i = 0; i < numsSize; i  )
    {
        sum  = nums[i];
    }

    return all - sum;
}

利用异或

首先要知道异或有一个特点，就是你拿一个数字去异或一个数字后，再拿这个异或完的数字去异或原来的其中一个数字，结果就是另一个一起异或的数字。 基于这个特点，我们有了这个思路：

用0去异或数组中的每一个数，然后再去异或0到n的每一个数字，最后结果就是消失的数字。

代码语言：javascript复制

int missingNumber(int* nums, int numsSize){
    int n=0;
    for(int i=0;i<numsSize;i  )
        n^=nums[i];
    for(int i=0;i<=numsSize;i  )//这里是n 1个数字，记得加上等于号
        n^=i;
    return n;
}

学到知识的朋友不要吝啬你们的赞哦(⊙o⊙)！

排序 数组

0 人点赞