leetcode刷题：消失的数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode刷题：消失的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

注意：本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

针对于这道题，我们提供了三种解法：

一、排序法遍历法

首先使用快排对数组进行排序，使其变成有序数组，由题意得知，在0~n的所有整数连续存放那的数组中前一个数字加一就是下一个数字的值，所以我们可以以这个为判断条件，遍历数组，当碰到不符合该条件的值时，直接跳出循环，我们就可以找出缺失的值是该下标对应值+1

int cmp(const int* e1 , const int* e2)
{
    return *e1 - *e2;
}
int missingNumber(int* nums, int numsSize){
    qsort(nums , numsSize , sizeof(int) , cmp);//1
    if(nums[0] != 0)
        return 0;
    int i = 0 ;
    while(i < numsSize && i+1 < numsSize)
    {
        if(nums[i+1] == nums[i] + 1)
        {
            i++;
        }
        else
        {
            break;
        }
    }
    return nums[i]+1;
}

要注意的是，当数组为{1}时，需要特殊判断一下，因为此时不会进入判断条件，直接执行最后一句话，造成错误。

二、计算总和法

思路：由题意，我们得知，假设一个是有n个数的数组，包含0~n的所有整数，其中缺失了一个，所以它必定多出了一个数字，因为数组的大小是固定的。所以我们利用循环，把0~(n+1)个数字累加到sum上，再让sum依次减去这个数组内的全部值，最终可以得到缺失的数字。

int missingNumber(int* nums, int numsSize){
    //采用相减的方法
    int i = 0;
    int sum = 0;
    for(i=0;i<=numsSize;i++)
    {
        sum += i;
    }
    for(i = 0 ;i<numsSize ;i++)
    {
        sum -= nums[i];
    }
    return sum;
}

三、按位异或法

通过对于“按位异或”操作符的理解我们知道：a^a= 0 , a^0 =a ,a^b^b=a^0 = a.

对于按位异或操作符不理解的可以看一下下面的博客：操作符详解（这么详细的操作符介绍你确定不看一看？）【C语言】【附试题详解】-CSDN博客

通过0按位异或一个数两次最终会得到0，我们可以进行以下设计：定义一个临时变量sum，让sum依次抑或0~(n+1)的值，然后再分别抑或这个缺失了数字的数组，最终的sum即为缺失的数字。文章来源地址https://www.toymoban.com/news/detail-820679.html

//采用位运算
//a^b^b = a
int missingNumber(int* nums, int numsSize){
    int i = 0 , sum =0;
    for(int i = 0; i <= numsSize ; i++)
    {
        sum ^= i;
    }
    for(i =0 ; i < numsSize ;i++)
    {
        sum ^= nums[i];
    }
    return sum ;
}

到了这里，关于leetcode刷题：消失的数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！