LeetCode刷题日记一(面试题17.04.消失的数字)

消失的数字

光学知识还不够，我们可以尝试去刷一些题目，今天小春宝带来的就是对一道经典题目消失的数字的题解

面试题 17.04. 消失的数字https://leetcode-cn.com/problems/missing-number-lcci/

消失的数字原题

提取关键信息

看到这道题，我们首先需要去提取一些重要信息

1.这个nums数组有numsSize个数也就是n个数

2.完整的数组nums应该是从0-n，有n+1个数

3我们需要返回那个消失的整数

思路一（暴力求解）

抛开时间复杂度o（N）不去谈我们首先应该想到的是暴力遍历这个数组，找到那个消失的数，第一种思路就是我们讲0-n中的每一个元素去对数组进行遍历，这种方法也是比较容易想到的

int missingNumber(int* nums, int numsSize) {
    int number = 0;   //作为寻找消失数字的钥匙
    for (int i = 0; i < numsSize; i++)
    {
        int flag = 0;//作为本次遍历是否有number的标记
        for (int j = 0; j < numsSize; j++)
        {
            if (number == nums[j])
            {
                flag = 1; //找到了，设置标记并跳出循环
                break;
            }
        }
        if (flag == 0)//说明本次循环没有number
        {
            return number;
        }
        number++;  //第一次遍历结束，number自加，flag重置
        flag = 0;
    }
    return number;
}

写完了题目，我们来分析一下这个算法，最坏情况消失的数字是n，我们需要进行n次遍历才能得到结果，每次遍历都要进行n步操作，时间复杂度为O(N*N),因为没有申请辅助空间，所以空间复杂度为O(1)，远远达不到题目要求，建议在没有思路的时候进行暴力求解

思路二（排序求解）

在乱序的情况下，我们进行遍历会消耗的时间非常大，当测试用例很大的时候很容易发生超时，所以我们可以先进行排序，再进行遍历就可以很快的找到这个消失的数字

1.第一步我们应该对数组进行排序，这里我们采用库函数qsort来进行，所以这一步我们需要调用qsort和设计cmp来进行比较

2.第二步我们要对数组进行一次遍历，如果前一个数和后一个数的差值不是1，说明中间有消失的数字，返回两个数的中间值即可

3.第二部遍历还存在着两种极端情况，如果消失的数字是0或者n时遍历不出结果，这个时候我们再对特殊情况进行单独考虑即可

int cmp(const void* e1, const void* e2) //设计比较函数
{
    return *(int*)e1 - *(int*)e2;
}
int missingNumber(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);  //进行快速排序
    for (int i = 0; i < numsSize - 1; i++)
    {
        if (nums[i] != nums[i + 1] - 1)  //判断是否有消失的数字
        {
            return nums[i] + 1;
        }
    }
    if (nums[0] != 0)   //消失的数字是0
    {
        return 0;
    }
    else      //消失的数组是n
    {
        return numsSize;
    }
}

这个算法实现以后，我们需要对其进行进行分析，我们进行了排序，快速排序的时间复杂度是O(logNN)，第二步我们进行了遍历时间复杂度为O(N)，第三步的时间复杂度是O(1)，总体来说时间复杂度是O（logNN），相比第一种算法已经有了很大的优化，但是依旧达不到要求

思路三（记数排序）

我们可以利用题目中提取的信息我们可以知道数组中的元素不重复，并且范围是从0-n，如果使用计数排序就可以对思路二的算法进行优化

1.第一步我们先动态开辟一个长度为numsSize+1的整型数组count，再对count数组进行初始化。

2.第二步遍历nums数组来修改count数组的内容

3.第三步遍历count数组找到那个消失的数字并返回

int missingNumber(int* nums, int numsSize) {
    int* count = (int*)malloc(sizeof(int) * (numsSize + 1));//开辟空间
    memset(count, 0, sizeof(int) * (numsSize + 1));//进行初始化
    for (int i = 0; i < numsSize; i++)
    {
        count[nums[i]] = 1;    //代表数字nums[i]存在
    }
    for (int i = 0; i < numsSize + 1; i++)
    {
        if (count[i] == 0)
        {
            return i;         //遍历count数组，若count[i]为0，则数组nums中无数字i
        }
    }
    return 0;    //使每一个执行路径都有返回值
}

那么我们继续计算算法的复杂度，我们其实只进行了计数，但并没有进行排序，但计数这一步就足够了，首先我们遍历了数组nums，时间复杂度为O(N)，接着我们遍历了数组count，时间复杂度为O(N),所以这个算法的时间复杂度是O(N),达到了题目要求，但是我们申请了一个n+1大小的数组，空间复杂度为O(N),接下来我们尝试O(1)的空间复杂度去解决这道题目

思路四（数组加减法）

接下来的思路也是利用了题目中的信息，数组的元素是从0-n，并且消失的数组只有一个，那么我们将数组的所有元素加起来然后用0-n的和去减掉数组元素和就可以得到消失的数字了

1.将数组的所有元素都加起来放进array_sum中去，再将1-n加起来放进n_sum中去

2.第二步用n_sum减去array_sum即可得到结果

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

这个算法我们只需要进行一次遍历，且只申请了常数个变量，时间复杂度O(N)，空间复杂度O(1)

虽然很完美的达到了题目要求，但是存在一定的隐患，如果n很大的时候可能会出现数据的溢出，所以我们可以想一想有没有更好的方法

思路五（异或）

有一个非常有趣的运算符异或^就可以轻松的解决这道题，主要利用异或的两个性质

1.自反性，异或两个同样的数结果为0，即a^a=0

2.任何数异或0都等于其本身，即a^0=a

知道了这些那么这道题就很好解决了

只需要将数组中的所有元素和1-n异或到一起就可以得到结果

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

这个算法只需要进行一次遍历，且不会出现数据溢出，并且只申请了一个变量大小的空间，所以这道题的时间复杂度为O(N)，空间复杂度为O(1)，为本道题的最佳解法

总结

这道题十分经典，思路也有很多种，当然，我相信还有更好的办法，欢迎在评论区点评！但不管是什么方法，这道题重要的都是提取关键信息，利用关键信息来去优化，重要的不是解出这道题，而是思考不同的方法然后想办法去实现的，摸索的过程，这道题整体上是不难的，谢谢大家的支持！