题目
解法一:
通过题目,给定了一个数组。
不难想到,我们可以先用排序算法对数组进行排序。
再使用一个复杂度为O(N)的循环进行比对,就可以解决这一道题。
1 | int Solution::missingNumber(vector<int> &nums){ |
因为c语言并没有预设排序函数,如果要使用这种解法,必须自己再造个轮子,所以选用这种解法并不优雅
。
使用排序函数会使程序运行时间在O(N)到O(N^2)
不等,由于题目上的说明,应将程序运行时间控制在O(N),故我们应当寻求更优解。
解法二:
使用排序函数会使程序变得相当慢,这次我们就从不排序下手。我们可以注意到。给定的数组是 0~n且少一个数字
。所以给定数组就是 n 个int
。
那么,我们可以创建一个 n+1个int
的数组 ,并使用三个复杂度为O(N)的循环解决就可以解决这道题。
1 | int Solution::missingNumber(vector<int> &nums) { |
这个方法的复杂度为O(N)
,虽然满足了将复杂度控制在O(N)
的条件,但事实上也是相当的不优雅。
可以注意到,我们额外创建了一个n+1的数组
。这会产生一个大问题,当数据量过大,会使你的内存占用变得相当的大。这是我们不想见到的,所以我们应当寻求更优解。
解法三:
这其实可以是一个简单的加减法问题。
可以利用高中知识将 0~n的总和算出来而我们可以将给定数组的值通过遍历求出来
我们将 0~n的总和 - 遍历总和 = 所求缺失数字
1 | int Solution::missingNumber(vector<int> &nums) { |
总结
以我目前的知识储备,我并没有得到该题的最优解。
我希望在接下来的学习中我能寻找到该题的最优解。
—–2020/7/13
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/13/学习笔记-Leetcode缺失的数字/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!