寻找消失的数字
🎈 作者:Linux猿
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
一、题目描述
给定一个包含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。
提示:
n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
进阶:你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
二、测试样例
输入:nums = [4,3,2,7,8,2,3,1]
输出:[5,6]
说明:在数组 nums 中,只有 5 和 6 没有出现在 [1,8] 的区间内。
三、算法思路
首先需要注意的是,本题要求使用的时间复杂度为 O(n),且不使用额外空间。
那么,可以确定的是只需要遍历常数次 nums 数组,不开辟额外的非常数级的空间,可以在原数组上修改,有这些条件限制后,能想到的解决方法就很局限了。
我们可以用下标标识[1, n] 之前的数字,遍历数组 nums,将以 nums[i] 为下标所标识的数组值加 n,一直遍历完数组,这样,如果 nums[i] < n ,表示 nums[i] 并没有加 n,所以 i 没有出现在[1,n]的区间中。
注意:因为是存储在数组中,下标从 0 开始,所以使用下标 i 表示数字 i - 1。
四、代码实现
五、复杂度分析
5.1 时间复杂度
时间复杂度:O(n),在上述算法中,使用了两层 for 循环,所以时间复杂度为 O(n)。
5.2 空间复杂度
空间复杂度:O(n),在上述算法中,使用 ans 存储最终的结果,所以空间复杂度为 O(n)。
六、总结
本题是一道很好的想法题,题目进行了很强的限制,需要结合题目限制来解题,这样更能想到解题方法。
🎈 作者:Linux猿
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
- 点赞
- 收藏
- 关注作者
评论(0)