消失的数字

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求：

链接：https://link.csdn.net/?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fmissing-number-lcci%2F

函数接口

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

方法1：求和相减

思路

1.先计算0-n元素的和 记为total

• 方法1：使用循环的方式求和 [0,numsSize]
• 方法2： *（等差数列求和 公式：（首项+末项）元素个数/2）
• 从0-n：元素个数为n+1 首项为0 末项为n

2.再计算数组所有元素相加的结果，记为sum，二者相减即为缺失的数字。

方法1：使用循环的方式求0-n的和

int missingNumber(int* nums, int numsSize) 
{
    int i = 0;
    int total = 0;
    int sum = 0;
    // 0 - n  共有n+1个数字
    //1.n+1个数字进行求和：
    for (i = 0; i <= numsSize; i++)
    {
        total += i;
    }
    //2.数组中的元素求和，
    //注意：数组元素个数为numsSize个，i的取值范围为[0,numsSize)
    for (i = 0; i < numsSize; i++)
    {
        sum += nums[i];
    }
    //3.二者相减的结果即为缺失的数字
    return total - sum;
}
int main()
{
    int arr[10] = { 3,4,5,7,2,1,6,0,8,9 };
    int ret = missingNumber(arr, 10);
    printf("%d\n", ret);
    return 0;
}

方法2：使用等差数列的方法求0-n的和

注意：0-n的元素个数为：n+1个

int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    int total = 0;
    int sum = 0;
    // 0 - n  共有n+1个数字
    //1.等差数列求和  ->公式 (首项+末项*元素个数)/2
    total = (0 + numsSize) * (numsSize+1) / 2;
    //2.数组中的元素求和，
    //注意：数组元素个数为numsSize个，i的取值范围为[0,numsSize)
    for (i = 0; i < numsSize; i++)
    {
        sum += nums[i];
    }
    //3.二者相减的结果即为缺失的数字
    return total - sum;
}
int main()
{
    int arr[10] = { 3,4,5,7,2,1,6,0,8,9 };
    int ret = missingNumber(arr, 10);
    printf("%d\n", ret);
    return 0;
}

方法2：排序之后比较

思路

• 1.使用排序算法，把数组中的元素进行从小到大排序(升序)
• 2.下标和数组下标内的元素进行比较是否相等。如果不相等，说明缺失的数字就是对应的下标
• 注意：数组元素为：numsSize个 0-numsSize：sunSize+1个元素
• 所以有可能缺少的时numsSize这个元素，前面的元素都匹配上了！！！！ 若不返回下标，就是返回numsSize！！！

int missingNumber(int* nums, int numsSize)
{
    //数组中元素个数为numsSize个
    //1.排序
    int i = 0;
    int j = 0;
    //共比较numsSize-1趟
    for (i = 0; i < numsSize - 1; i++)
    {
        int flag = 1;   // 假设已经有序
        //每一趟可以少比较一个元素
        for (j = 0; j < numsSize - 1 - i; j++)
        {  
           //排成升序
            if (nums[j] > nums[j + 1])
            {
                flag = 0;
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
        if (flag == 1)
        {
            //说明已经有序
            break;
        }
    }
    //2.比较
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] != i)
        {
            return i;
        }
    }
   //有可能缺少的时numsSize这个元素，前面的元素都匹配上了！！！！
    return numsSize;
}

方法3：异或

使用异或

异或的特点：

1.异或：两数对应的二进制位，相同为0，不同为1.

2.相同的数进行异或结果为0 a^a = 0

3.0和任何数异或为该数本身 0^a =a

4.由上述我们可以知道：a^b^a = b

思路

1.定义一个变量x初始化为0 (0和任何数异或->结果为本身)

2.数组遍历与x进行异或

3.最后x再与0-n的数异或，最后x的值就是缺失的数

int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    int x = 0;
    //1.x与数组中所有元素异或
    for (i = 0; i < numsSize; i++)
    {
        x ^= nums[i];
    }
    //异或之后的结果与0-numsSize直接的数进行异或
    for (i = 0; i <= numsSize; i++)
    {
        x ^= i;
    }
    //最后x的值就是缺失的数字
    return x;
}
int main()
{
    int arr[10] = { 3,4,5,7,2,1,6,0,10,9 };
    int ret = missingNumber(arr, 10);
    printf("%d\n", ret);
    return 0;
}

注意事项：x与0-numsSize的数字进行异或时循环判断条件为 i<=numsSize 0-numsSize之间的元素个数：numsSize+1个

因为数组有numsSize个数，因为缺了1个 所 以实际有numsSize+1个数

\