重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
【C语言】LeetCode面试题17.04.消失的数字的n种解法-创新互联
本文涉及的库函数或者数据结构与算法不熟悉的地方，可以在文章末找到相关知识详解链接。
- 题目描述
- 解法一
- 题解代码
- 解法二
- 题解代码
- 解法三
- 题解代码
- 解法四
- 题解代码
- 总结
OJ链接：LeetCode 面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
题目中描述，数组nums包含从0到n的所有整数，但缺少了其中一个。
那么我们可以通过等差数列求和公式，或者0-n循环求和，都可以得到总和totalNum。我们只需要再遍历减去数组的各个元素，剩下的值就是消失的数字了。
时间复杂度O(n)，空间复杂度O(1)。
//nums是题目给我们的数组，numsSize是数组的大小
int missingNumber(int *nums, int numsSize)
{//等差数列求和公式 项数*（首项+尾项）/2
//我们要求0-n，有n+1项，首项为0，尾项为n，numsSize大小是n
int totalNum = (numsSize + 1) * (0 + numsSize) / 2;
//遍历减去已有数
for (int i = 0; i< numsSize; i++)
totalNum -= nums[i];
//此时返回值totalNum就是missingNum
return totalNum;
}//timeO(n) spaceO(1)我们知道异或^位运算符（二进制位相同为0，相异为1）有这样的性质：
- 数字与自己本身异或为0，5^5=0
- 数字与0异或还是自己本身，7^0=7，0二进制位全是0，和0相同的就是0，相异的就是1，不变
所以我们可以定义个数字Num=0，然后让他与0-n各个数字遍历异或，再把他与nums各个元素异或，存在的数字就会异或两遍得0，不会对Num造成影响，最后只有落单的消失的数字，与Num=0异或，是Num值变为消失的数字值。
时间复杂度O(n)，空间复杂度O(1)。
int missingNumber(int *nums, int numsSize)
{//从0-n遍历异或一遍
int Num = 0;
for (int i = 0; i<= numsSize; i++)
Num ^= i;
//再把nums各个元素异或一遍
for (int i = 0; i< numsSize; i++)
Num ^= nums[i];
//此时的Num的值就是missingNum
return Num;
}//timeO(n) spaceO(1)nums是0-n中消失了一个数的数组，如果我们自定义一个n+1大小的数组arr并赋值为0，用nums各个元素做下标，如果数字存在，则把数组arr对应位置下标元素赋值为1，再遍历一次查找哪个下标值为0，就找到消失的数字了。
时间复杂度O(n)，空间复杂度O(n)
int missingNumber(int *nums, int numsSize)
{//开辟一个n+1大的数组，并赋值为0
int *arr = (int *)malloc((numsSize + 1) * sizeof(int));
memset(arr,0, (numsSize + 1) * sizeof(int));
//数字存在则把对应数组下标位置赋值为1
for (int i = 0; i< numsSize; i++)
arr[nums[i]] = 1;
//当arr值为0会停止循环，此时的值就是消失的数字
int missNum = 0;
while (arr[missNum])
missNum++;
return missNum;
}//timeO(n) spaceO(n)我们还可以把数组进行快速排序，再从0开始用二分查找法遍历查找数字是否存在。
快速排序时间复杂度O(nlogn)，空间复杂度O(logn)。
二分查找时间复杂度O(logn)，空间复杂度O(1)。
所以此题解时间复杂度O(nlogn)，空间复杂度O(logn)。
代码可能跑不过OJ会挂。
int int_cmp(const void *e1, const void *e2)
{return *(int *)e1 - *(int *)e2;
}
int missingNumber(int *nums, int numsSize)
{//先将数组快排
qsort(nums, numsSize, sizeof(int), int_cmp);
//从0-n逐个数字二分查找, 没查找到的数字就是
//flag用来标记数字是否查找到
int flag = 0;
int begin = 0;
int end = numsSize - 1;
int mid = (begin + end) / 2;
int missNum = 0;
for (missNum = 0; missNum<= numsSize; missNum++)
{//二分查找
while (begin<= end)
{if (nums[mid] >missNum)
{end = mid - 1;
}
else if (nums[mid]< missNum)
{begin = mid + 1;
}
else
{flag = 1;
break;
}
mid = (begin + end) / 2;
}
//没有查找到，终止for循环
if (!flag)
{break;
}
//查找到了，初始化二分查找的基本变量，进入下次循环
else
{ begin = 0;
end = numsSize - 1;
mid = (begin + end) / 2;
flag = 0;
}
}
return missNum;
}//timeO(nlogn) spaceO(logn)解法一简单易想，时间复杂度和空间复杂度都最佳。
解法二巧妙利用了位运算异或^的特性，十分巧妙，时间和空间复杂度也很佳，也是本文主要想介绍的解法。
解法三利用数组下标和对应元素值的映射，解法也不错。
解法四暴力的遍历查找，可以解决问题，但时间复杂度太高。
memset内存赋值函数详解
qsort快速排序函数详解
码字不容易，欢迎关注，点赞，收藏，评论，转发。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：【C语言】LeetCode面试题17.04.消失的数字的n种解法-创新互联
文章网址：http://cqcxhl.com/article/pejej.html