448.找到所有数组中消失的数字
【LetMeFly】三种方法解决:448.找到所有数组中消失的数字
力扣题目链接:https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/
给你一个含 n
个整数的数组 nums
,其中 nums[i]
在区间 [1, n]
内。请你找出所有在 [1, n]
范围内但没有出现在 nums
中的数字,并以数组的形式返回结果。
示例 1:
输入:nums = [4,3,2,7,8,2,3,1] 输出:[5,6]
示例 2:
输入:nums = [1,1] 输出:[2]
提示:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶:你能在不使用额外空间且时间复杂度为 O(n)
的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
方法一:哈希
方法一实现起来很简单,使用一个哈希表存放出现过的元素,再从$1$到$n$遍历一遍看哪个元素没有在哈希表中,哪个元素就“没有出现过”
- 时间复杂度$O(n)$,其中$n$是数组中元素个数
- 空间复杂度$O(n)$,空间复杂度主要来自哈希表
AC代码
C++
1 |
|
方法二:原地修改
方法一的空间复杂度主要来自哈希表
那么想要不额外开辟空间,有种办法就是在原始数组上修改。
如果原始数组中存在$x$,那么我们就把原始数组的第$x$个数变成负数。
这样,我们只需要从第一个数遍历到第$n$个数,看看哪个数是正数(假设是第$a$个),就说$a$没有在数组中出现过。
但是代价是,我们修改了原始数组!!!
- 时间复杂度$O(n)$,其中$n$是数组中元素个数
- 空间复杂度$O(1)$,如果原始数组不允许修改,则此方法无效
AC代码
C++
1 |
|
方法三:双指针
不如给原始数组排个序,然后用一个“指针”指向数组中处理过的元素,另一个“指针”从“1”指到“n”
指针二从1到n遍历,当指针一所指位置合法并且所指元素小于指针二时,指针一后移
接着判断指针一所指是否和指针二相同,相同则表示指针二所指出现过,否则表示没有出现过
- 时间复杂度$O(n\log n)$,其中$n$是数组中元素个数
- 空间复杂度$O(\log n)$,空间复杂度来源主要是排序
AC代码
C++
1 |
|
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/127421428
448.找到所有数组中消失的数字
https://blog.letmefly.xyz/2022/10/20/LeetCode 0448.找到所有数组中消失的数字/