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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
unordered_set<int> se;
for (int& t : nums)
se.insert(t);
vector<int> ans;
int n = nums.size();
for (int i = 1; i <= n; i++) {
if (!se.count(i))
ans.push_back(i);
}
return ans;
}
};

方法二:原地修改

方法一的空间复杂度主要来自哈希表

那么想要不额外开辟空间,有种办法就是在原始数组上修改。

如果原始数组中存在$x$,那么我们就把原始数组的第$x$个数变成负数。

这样,我们只需要从第一个数遍历到第$n$个数,看看哪个数是正数(假设是第$a$个),就说$a$没有在数组中出现过。

但是代价是,我们修改了原始数组!!!

  • 时间复杂度$O(n)$,其中$n$是数组中元素个数
  • 空间复杂度$O(1)$,如果原始数组不允许修改,则此方法无效

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int& t : nums) {
int loc = abs(t) - 1;
nums[loc] = -abs(nums[loc]);
}
vector<int> ans;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] > 0)
ans.push_back(i + 1);
}
return ans;
}
};

方法三:双指针

不如给原始数组排个序,然后用一个“指针”指向数组中处理过的元素,另一个“指针”从“1”指到“n”

指针二从1到n遍历,当指针一所指位置合法并且所指元素小于指针二时,指针一后移

接着判断指针一所指是否和指针二相同,相同则表示指针二所指出现过,否则表示没有出现过

  • 时间复杂度$O(n\log n)$,其中$n$是数组中元素个数
  • 空间复杂度$O(\log n)$,空间复杂度来源主要是排序

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> ans;
int n = nums.size();
int loc = 0;
for (int to = 1; to <= n; to++) {
while (loc < n && nums[loc] < to)
loc++;
if (loc == n || nums[loc] != to)
ans.push_back(to);
}
return ans;
}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/127421428


448.找到所有数组中消失的数字
https://blog.letmefly.xyz/2022/10/20/LeetCode 0448.找到所有数组中消失的数字/
作者
Tisfy
发布于
2022年10月20日
许可协议