【快乐手撕LeetCode题解系列】——消失的数字

😎博客昵称：博客小梦

😊最喜欢的座右铭：全神贯注的上吧！！！

😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！

😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

   哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，和大家分享【快乐手撕LeetCode题解系列】——消失的数字~ 都是精华内容，可不要错过哟！！！😍😍😍

消失的数字🙌

做题准备：

1.首先认真审题，冷静分析，先尽量找到解决问题的所有算法，然后再从陈中选择最好的算法。

2.这里一共将介绍三种解题方法，并分析出每一种算法的时间复杂度和空间复杂度，分享我的一些解题经验。

解题思路分析：😍

解题思路一 ：源代码分享：😍

1.首先通过malloc函数动态开辟一个数组，将原来nums数组中的每一个元素存放到开辟的p数组对应的下标位置里面；

2.然后对数组p的元素全部赋值为-1，只要不是0~n的数字就行了；

3.将nums数组的元素存放到p数组对应的数组下标的位置上。例如将3存放到p[3]位置上。

4.最后遍历一遍数组p，还存放着-1的位置的数组下标 i 就是那个消失的数字

int missingNumber(int* nums, int numsSze)
{
    int *p = (int*)malloc(sizeof(int)*(numsSze+1));
    int i = 0;
    for (i = 0; i < numsSze + 1; i++)
    {
        p[i] = -1;
    }
    for (i = 0; i < numsSze; i++)
    {
        p[nums[i]] = nums[i];
    }
    for(i = 0 ; i < numsSze + 1; i++)
    {
        if(p[i] == -1)
        return i;
    }
    return 0;
}

解题思路二 ：源代码分享：😍

• 1.利用异或的思路，将消失的数字找出来。
• 2.首先先让 x 赋值为0；
• 3.然后让 x 和 0 到 numsSze 的数字进行一个异或；
• 4.再让 x 和 nums数组的每一个元素进行一个异或；
• 5.而我们的答案就是只出现一次的数字；
• 6.最后异或的结果就是我们要求的消失的数字啦！
• 7.0 的任何数异等于它本身；
• 8.相同的数异或为0

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

解题思路三 ：源代码分享：😍

• 数学公式法求解此题。这里可以运用等差数列的求和公式 来求解
• 等差数列的求和公式 ：（首项 + 最后一项） x 项数 / 2。
• 利用公式将所有的完整顺序的所有数字都相加起来，然后减去nums数组的每一个元素，剩下的就是那个消失的数字啦！

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

程序输出结果验证： 😊

总结撒花💞

   本篇文章旨在分享【【快乐手撕LeetCode题解系列】——消失的数字。希望大家通过阅读此文有所收获！😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘