题目
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
排序法
第一种方法，需要用到qsort函数，先将数组按从小到大排好序，然后遍历，当下标与该数组元素不相等时，返回这个数组元素的值。
冒泡排序的时间复杂度是o(n^2)，而快速排序的时间复杂度是o(n*logn)，我们选择效率更优的快速排序。 排序之后我们需要遍历数组，那程序总共需要执行n*logn+n次。
时间复杂度是o(n*logn)。
#include<stdio.h> #include<stdlib.h> int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; //由小到大排序 //return *(int *)b - *(int *)a; 由大到小排序 } int missingNumber(int* nums, int NumsSize) { int i; qsort(nums, NumsSize, sizeof(nums[0]), cmp); for (i = 0; i <=NumsSize; i++) { if (i != nums[i]) { return i; } } return -1; } int main() { int a[] = {7,9,10 ,0,3,4,1,2,5,6}; if (missingNumber(a, sizeof(a) / sizeof(a[0])) == -1) { printf("未找到\n"); } else printf("%d",missingNumber(a, sizeof(a) / sizeof(a[0]))); return 0; }
异或法
异或，这个方法思路类似于之前找单身狗那道题，异或的两个元素相同为0，相异为1。
要注意第二次遍历次数是数组大小加一，原因是要加上缺失的那一个元素。
除了缺失的元素，其余元素异或的结果一定为0，所以第二次异或的结果一定是缺失的元素值。
程序要执行2n次。
时间复杂度：o(n)，比第一种效率更高。
#include<stdio.h> #include<string.h> int main() { int a[] = { 7,9,10 ,0,3,4,1,2,5,6 }; int i = 0; int x = 0; while (i <sizeof(a)/sizeof(a[0])) { x ^= a[i]; i++; } for (i = 1; i <= sizeof(a)/sizeof(a[0]) + 1; i++) { x ^= i; } printf("%d", x); return 0; }
最天才的方法
鬼才才能想出来的方法，果然是大道至简！
第一次遍历将整个数组以及缺失的元素加到一起。
第二次遍历将原数组的值挨个减掉，这样最后剩下的值一定就是所缺失的元素。
时间复杂度是惊人的o(n),芜湖，最好使竟是最单纯的，感动了！
int missingNumber(int* nums, int numsSize) { int sum = 0; for (int i = 0; i < numsSize + 1; i++) { sum += i; } for (int i = 0; i < numsSize; i++) { sum -= nums[i]; } return sum; }
总结
感谢观看，本文到这里就结束了，如果觉得有帮助，请给文章点个赞吧，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！下期再见。🎉
