题目分析
这个题目我做过许多次了,之前是使用Python语言写的代码,这次用C++来实现一下,题目难度不大,小伙伴们能够想到多少种方法呢?
暴力法
直接遍历查找,每一个数都从数组中进行查找,看一下是否存在。
算法的**时间复杂度为$O(n^2)$,空间复杂度为$O(1)$**。
提交时会TLE,因此不能使用这个方法。
1 | #include<iostream> |
数组
使用空间来换取时间,来一个数则该索引值+1,最后遍历数组,看一下哪一个索引对应的值为0即可。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
哈希表
使用哈希表同样的道理,可以先将0~n的所有元素都加入哈希表中,然后从nums中逐一删除,最后剩余元素就是缺失的元素。
也可以从nums中逐一添加进哈希表,然后查找0~n的所有元素,如果找不到说明该元素是缺失元素,
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
优化数组
都是正数的题目可以在原数组上进行修改,不需要另外开辟数组。
如果某个数等于k,那么我们让k对应的索引变成相反数。那么最后是正数的位置说明没有相应的k让其变化。
但是这个方法需要考虑很多的情况,代码量较长。
- 最大值问题,数组长度为n,最大值为n,因此不能改变nums[n]对应的值,会数组越界。因此我们要对最大值进行特判。
- 0的问题,如果某个位置的值是0,如nums[k] = 0,那么我们修改k的时候还是0,最后查询时会出错。因此我们先判断0是否存在,如果不存在直接返回0。如果存在,我们对修改后的数组查询时,如果存在正数,则返回对应索引,如果不存在,说明恰好修改的是0,因此返回0的索引。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
数学
在优化数组中,我们遍历了数组4次,如何更快更高效呢?
数组中的数组是从0~n的,因此和是已知的,我们计算之和,然后再减数组中的每一个元素,即可求出缺失元素。
在Python中不会超出数据的表示范围,但是C++中要小心,因此利用等差数列求和公式是不安全的,这里给出一种更好的处理方法。
我们要计算0~n这n个数的和,然后减去nums数组中的和,可以减去数组中的元素,如果结果小于等于0,那么就加上一个数k,直到结果变为正数为止,其中k从0到n。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
位运算
本题除了数学方法以外,也有其他巧妙的方法——位运算。
位运算是满足交换律的,而且满足如下两个式子。
$x ^ x = 0 \ \ x ^ 0 = x$
因此我们先从0异或到n,再异或数组中的所有元素,那么除了缺失的元素以外,其他的元素都异或了两次,都变成了0,0异或缺失的元素,最后得到的结果就是缺失的元素。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
刷题总结
题目虽然简单,但是考察了许多重要的知识点,如数据的表示范围,位运算等等,希望小伙伴们能够掌握后面三种方法。