每日一题---OJ题: 消失的数字

片头

嗨! 小伙伴们大家好! 我们又见面啦,今天我们一起来看看这道题

这道题看上去挺简单的,我们这里提供3种思路:

思路1: 先排序,再找出后一个不等于前一个加1 ,那后一个就是消失的数字

代码如下:

int missingNumber(int* nums, int numsSize) {
    //先排序
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j <= numsSize - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                //交换
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }

    //若后一个不等于前一个加1,那么后一个就是消失的数字
    int k = 0;
    for ( k = 0; k < numsSize; k++) {
        if (nums[k] + 1 != nums[k + 1]) {
            break;
        }
    }
    return nums[k] + 1;
}

int main() {
	//先排序(冒泡)
    int arr[] = { 9,6,4,2,3,5,7,0,1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int ret = missingNumber(arr, size);
    printf("%d\n", ret);
	return 0;
}

运行结果为:

8 

But, 虽然我们在VS上面跑的过去,但是提交到leetcode就不行了 

为啥会是这样???

哈哈哈,那是因为我们没有好好审题 !   !   ! 

让我们来看看题目要求:

 题目要求我们在时间复杂度为 O(n) ,但是冒泡排序的时间复杂度为 O(n^2),很明显,不符合题意。

那就换一种思路呗！

思路2 ： 定义一个变量x, x先和 0~n 中的所有值异或,再跟数组中的值异或,时间复杂度为 O(n)

思路分析: 为啥是这样的思路呢? 因为,异或的定义: 相同为0, 相异为1 ,先用x将 0~n 异或的结果保存起来,再和数组中的值进行异或, 如果数组中的值和 我们之前异或的值相同, 那么这个数就消失了; 如果这个数不在数组里面, 那么最后只会剩下这一个数。

代码如下：

int missingNumber(int* nums, int numsSize) {
    //定义一个变量x,x的初始值为0
    int x = 0;
    for (int i = 0; i <= numsSize; i++) {
        x ^= i; //将 x 和 0~numSize 的每一个值进行异或
    }

    for (int j = 0; j < numsSize; j++) {
        x ^= nums[j];//将 x 和 数组中的每一个值进行异或
    }
    return x;        //将最后剩下的数返回
}

int main() {
    int arr[] = { 9,6,4,2,3,5,7,0,1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int ret = missingNumber(arr, size);
    printf("%d\n", ret);
	return 0;
}

运行结果为：

8 

同时，leetcode也显示通过

哈哈哈, 是不是就只有一种方法呢? 当然不是啦,还有另外一种思路,小学生都会 !    !    ! 

思路3 : 定义一个变量ret , 先计算 0~n 的累加和, 再用累加和依次减去数组中的值, 时间复杂度为 O(n)

是不是很简单?

代码如下:

int missingNumber(int* nums, int numsSize) {
    //计算 0~numSize 累加和,累加和依次减去数组中的值
    int ret = 0;
    for (int i = 0; i <= numsSize; i++) {
        ret += i;
    }
    for (int j = 0; j < numsSize; j++) {
        ret -= nums[j];
    }
    return ret;
}

int main() {
    int arr[] = { 9,6,4,2,3,5,7,0,1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int ret = missingNumber(arr, size);
    printf("%d\n", ret);
	return 0;
}

运行结果为:

8 

同时,leetcode也提交通过

片尾

今天我们学习了消失的数字这道OJ题,希望看完这篇文章能对友友们有所帮助  !    !    !

求点赞收藏加关注 !   !   ! 

谢谢大家 !   !    !