一、题目描述

oj链接：https://leetcode.cn/problems/missing-number-lcci

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

二、题目分析

此题目要求算法在O(N)时间内完成，也就是说时间复杂度不超过O(N)，我们要找出数组nums中缺少的数有以下几种办法：

2.1 方法一

2.1.1 思路

方法一主要是通过求和相减找出0-n中缺失的那个数，先将0到n之间的数相加求和，然后依次减去数组中的每个数，得到的就是缺失的那个数。

注意这里求0到n的数相加的和我们使用了等差数列的求和公式：sum(和) = (n+1)*n/2.

方法一的时间复杂度是：O(N)，我们要将0到n的和依次减去数组中的元素，所以在这里我们需要遍历一遍数组，即执行n次循环，所以时间复杂度是O(N)，他的空间复杂度是：O(1)，这个算法只额外开辟了几个变量，属于是常数阶，用O(1)来表示空间复杂度。

2.1.2 代码

int missingNumberTwo(int* nums, int n)
{int sum = n * (n + 1) / 2;int i = 0;for (i = 0; i < n; i++){sum -= nums[i];}return sum;
}

2.2 方法二

2.2.1 思路

方法二主要是通过异或找出0-n中缺失的那个数，在之前的博客：<操作符详解>中具体对异或进行了解释，如果不太清楚可以去看看。

对于任何一个数和0异或得到的都是他本身，一个数和自己异或得到的是0，并且异或是满足交换律的，因此根据这一规律，我们就可以找到0-n中缺失的那个数，先将定义一个变量x将他初始化为0，让他先和数组中的每个数进行异或操作，然后再与0到n的每个数进行异或操作，如果某个数在数组中和0-n中都存在，异或之后为0，如果有单独的一个数只在0-n中存在，而不在数组中，异或之后也无法消去，将0分别与数组中的数以及0-n之间的数异或，最后得到的就是缺失的那个数。

方法二的时间复杂度是：O(N)，我们要将0分别与数组中的数以及0-n之间的数异或，需要遍历一次数组和依次0-n之间的数，即执行2n次循环，所以时间复杂度是O(N)，他的空间复杂度是：O(1)，这个算法只额外开辟了几个变量，属于是常数阶，用O(1)来表示空间复杂度。

2.2.2 代码

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

2.3 方法三

2.3.1 思路

方法三主要是先对数组进行排序处理，然后使用二分查找，在这里对数组排序我们使用的是qsort库函数，使用qsort库函数还要提供一个比较函数compar。

方法三的时间复杂度是：O(N*logN)，在这个算法中，我们要求时间复杂度，分开来看，二分查找的时间复杂度是O(logN)，qsort的时间复杂度是O(N*logN)，按照大O的渐进表示法，此算法的时间复杂度是O(N*logN)。

注意题目中要求时间复杂度不超过O(N)，所以这个思路在力扣上不会通过，仅仅提供一种参考思路。

2.3.2 代码

int compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i = 0;for (i = 0; i <= n; i++){int exchange = 1;int begin = 0;int end = n - 1;while (begin <= end){ int mid = (begin + end) / 2;if (i > nums[mid])begin = mid + 1;else if (i < nums[mid])end = mid - 1;else{exchange = 0;break;}}if (exchange == 1){return i;}}
}

三、完整代码

这道题是属于oj类型的题目，所以在拿到vs上编译的时候，需要自己写一个主函数，在这里我们提供一个完整的函数。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>int compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberOne(int* nums, int n)
{int x = 0;for (int i = 0; i < n; i++){x ^= nums[i];}for (int i = 0; i < n + 1; i++){x ^= i;}return x;
}int missingNumberTwo(int* nums, int n)
{int sum = n * (n + 1) / 2;int i = 0;for (i = 0; i < n; i++){sum -= nums[i];}return sum;
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i = 0;for (i = 0; i <= n; i++){int exchange = 1;int begin = 0;int end = n - 1;while (begin <= end){ int mid = (begin + end) / 2;if (i > nums[mid])begin = mid + 1;else if (i < nums[mid])end = mid - 1;else{exchange = 0;break;}}if (exchange == 1){return i;}}
}int main()
{int nums[5] = { 0 };int i = 0;int n = sizeof(nums) / sizeof(nums[0]);for (i = 0; i < n ; i++){scanf("%d", &nums[i]);}//1.异或int x = missingNumberOne(nums, n);printf("%d\n", x);//2.求和再相减x = missingNumberTwo(nums, n);printf("%d\n", x);//3.排序+二分查找x = missingNumberThree(nums, n);printf("%d\n", x);return  0;
}