一、问题描述
问题的要点:
- 数组中存储了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; }