ledcode----丢失的数字

目录

题目截图：

 题目接口：

第一种解法：

思路：

第二种解法：差值法

思路：

第三种解法：位运算异或法

关于异或操作符的预备知识：

思路：

例子：输入数组[0，1，3]。根据题目要求消失的数字就是2，n=3。

结语：

题目截图：

 题目接口：

int missingNumber(int* nums, int numsSize){

}

第一种解法：

思路：

第一步，定义一个长度为10000的数组（题目中的数组长度最大为10000）并将数组中的数据初始化为0。

第二步，将nums中的数据作为下标对arr进行赋值为1的操作。

第三步,对arr进行遍历，当arr[i]==0时成立时返回下标i，这里的i就是缺失的数字。

int missingNumber(int* nums, int numsSize) {
   
    int arr[10000] = { 0 };
    int i = 0;
    for (i = 0;i < numsSize;i++) {
        arr[nums[i]] = 1;
    }
    for (i = 0;i < numsSize + 1;i++) {
        if (arr[i] == 0)
            break;
    }
    return i;
}

第二种解法：差值法

思路：

第一步，对0~n的数字进行加和

第二步，对数组中的元素进行加和

第三步，返回两个数的差值，这个差值就是丢失的数字。

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

第三种解法：位运算异或法

关于异或操作符的预备知识：

1.0^(任何数）=任何数   0^1=1;

2.两个相等的数字异或自己=0  1^1=0;

3.异或操作支持交换律。

思路：

第一步，先定义一个x=0

第二步，使用x来异或数组中每一个元素，并将x赋值为x^nums[i].

第三步，用第一个循环中得到的数来异或0~n的数，并对x重新赋值

第四步，两循环结束以后得到的x的值就是丢失的数字。

例子：输入数组[0，1，3]。根据题目要求消失的数字就是2，n=3。

执行程序后的操作：x=0^0^1^3^0^1^2^3=0^0^0^1^1^2^3^3=0^2=2

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

结语：

小牛儿今天的分享就到这里了，如果有错误的话请指正。如果对你的学习有帮助的话，请给小牛儿来个三连吧。