【Leetcode】消失的数字 [C语言实现]
👻内容专栏：《Leetcode刷题专栏》
🐨本文概括： 面试17.04.消失的数字
🐼本文作者：花 碟
🐸发布时间：2023.4.10
目录
思想1：先排序再查找
思想2：异或运算
代码实现：
思想3：等差数列求和相减
代码实现：
点击跳转到Leetcode的OJ平台 17.04 消失的数字
题目：
数组
nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？int missingNumber(int* nums, int numsSize);
示例1：
示例2：
分析：
1.数组中经过排列后是一串有序列的整数，只不过序列中缺失了一个整数，题目需要让你找出这个缺失的数字。
2.时间复杂度要求允许在O(n)范围内。
思想1：先排序再查找
首先，我们就可以想到将数组nums里的元素进行排序，然后进行依次查找，如果下一个数不是上一个数+1得到的，那么上一个数+1就是我们要找的消失的数字。这题，按道理可以这么去写。
但是，观察各类常见的排序算法的时间复杂度详解图，最坏情况达不到我们该题要求的时间复杂度之内，在这里我们去运用排序，并不太合适。
| 类别 | 排序方法 | 时间复杂度 | ||
|---|---|---|---|---|
| 平均情况 | 最好情况 | 最坏情况 | ||
| 插入排序 | 直接插入 | O(n²) | O(n) | O(n²) |
| 希尔排序 | O(n¹·³) | O(n) | O(n²) | |
| 选择排序 | 直接排序 | O(n²) | O(n²) | O(n²) |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | |
| 交换排序 | 冒泡排序 | O(n²) | O(n) | O(n²) |
| 快速排序 | O(nlog₂n) | O(nlog₂n) | O(n²) | |
| 归并排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | |
| 基数排序 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | |
| 注：基数排序的复杂度中，r代表关键字的基数，d代表长度，n代表关键字的个数 | ||||
接下来，我们寻找其他方法击破此题。
思想2：异或运算
我们利用异或运算的规则（相同为0，相异为1），我可以先让一个变量x，初始值为0，与数组nums中numSize个元素进行异或运算，最后再与0 ~ numSize循环遍历的值进行异或，就能够得到是一个落单的数字，也就是我们最后要找的“消失的数字”
代码实现：
int missingNumber(int* nums, int numsSize){int i = 0;int x = 0;for(i = 0;i < numsSize;i++){x ^= nums[i];}for(i = 0;i <= numsSize;i++){x ^= i;}return x;
}思想3：等差数列求和相减
我们可以写一个循环计算0~numSize所有数字之和，0到numSize个数字本质也是一个等差数列，也可以使用等差数列求和公式，得出一个sum1值。继续求出nums数组中所有整数之和，得出一个sum2值。sum1减去sum2得到的数字就是“消失的数字”
代码实现：
int missingNumber(int* nums, int numsSize){int i = 0;int sum1 = (1 + numsSize)*numsSize / 2;int sum2 = 0;for(i = 0;i < numsSize;i++){sum2 += nums[i];}return sum1 - sum2;
}🤗🤗 好啦，本篇文章的创作就到此为止啦，如有不当，还请私信我纠正哦~