【C语言指南】消失的数字
【摘要】 如果用暴力解法:先将数组排序，再对数组每个元素与相邻元素进行比对的方法，受制于排序的时间复杂度至少为O（nlogn），所以这种方法是行不通的。
对时间复杂度优化
先将0到n相加求和，再将数组元素求和，两个结果作差就是缺失的数字，时间复杂度为O（n）。相加求和的方法，对于数组元素较大的情况，无法正确处理
这里使用异或的方法来解决
目录
一、问题描述
问题的要点：
- 数组中存储了0到n的数字，但缺失了一个
- 数组是无序的
- 时间复杂度要求 O（n）
二、解题思路
题目要求时间复杂度为O（n）
如果用暴力解法:先将数组排序，再对数组每个元素与相邻元素进行比对的方法，受制于排序的时间复杂度至少为O（nlogn），所以这种方法是行不通的
方法一:求和做差
对时间复杂度优化
先将0到n相加求和，再将数组元素求和，两个结果作差就是缺失的数字
用两个循环求和，时间复杂度为O（n）
该算法可以进一步优化:
0到n求和可以使用等差数列求和的公式（ （首项+尾项)*项数/2)，直接求出结果
不过时间复杂度已不能进一步降低了
方法二:异或
相加求和的方法，对于数组元素较大的情况，无法正确处理
这里使用异或的方法来解决——
将数组每个元素异或一遍，再跟0到n依次异或，得到的结果就是缺失的数字（原理是任意两个相同的数字异或，结果为0；0与任何数字异或，结果是该数字本身）
时间复杂度为O（n）
三、C语言代码实现
方法一实现：
int missingNumber1(int* nums, int numsSize)
{
int sum1 = (0 + numsSize) * (numsSize + 1) / 2;//0到numsSize求和
int sum2 = 0;
for (int i = 0; i < numsSize; i++)//数组求和
{
sum2 += nums[i];
}
return sum1 - sum2;//做差
}方法二实现：
int missingNumber2(int* nums, int numsSize)
{
int ret = 0;
for (int i = 0; i <= numsSize; i++)//与0到numsSize异或
{
ret ^= i;
}
for (int i = 0; i < numsSize; i++)//与数组每个元素异或
{
ret ^= nums[i];
}
return ret;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）