找到所有数组中消失的数字
难度:
标签:
题目描述
给你一个含 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)
的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
代码结果
运行时间: 38 ms, 内存: 25.2 MB
/*
* 题目思路:
* 使用 Java Stream API 解决问题,我们先创建一个包含 [1, n] 的完整集合,然后移除所有在 nums 数组中出现的数字。
* 具体步骤是:
* 1. 通过 IntStream 生成 [1, n] 范围的数字流。
* 2. 使用 filter 方法过滤掉存在于 nums 数组中的数字。
* 3. 将剩余数字收集为一个列表。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
Set<Integer> numSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
return IntStream.rangeClosed(1, nums.length)
.filter(num -> !numSet.contains(num))
.boxed()
.collect(Collectors.toList());
}
}
解释
方法:
该题解的思路是先将原数组转换为集合,然后遍历从1到n的所有数字,检查每个数字是否在集合中。如果不在集合中,则说明该数字在原数组中消失,将其添加到结果数组中。最后返回结果数组。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在确定一个数字是否消失时,你是怎么考虑数组中存在重复数字的情况的?
▷🦆
这种方法对于极大或极小的n表现如何?是否有必要对特殊情况进行优化?
▷相关问题
缺失的第一个正数
给你一个未排序的整数数组 nums
,请你找出其中没有出现的最小的正整数。
O(n)
并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0] 输出:3 解释:范围 [1,2] 中的数字都在数组中。
示例 2:
输入:nums = [3,4,-1,1] 输出:2 解释:1 在数组中,但 2 没有。
示例 3:
输入:nums = [7,8,9,11,12] 输出:1 解释:最小的正数 1 没有出现。
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
数组中重复的数据
给你一个长度为 n
的整数数组 nums
,其中 nums
的所有整数都在范围 [1, n]
内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n)
且仅使用常量额外空间的算法解决此问题。
示例 1:
输入:nums = [4,3,2,7,8,2,3,1] 输出:[2,3]
示例 2:
输入:nums = [1,1,2] 输出:[1]
示例 3:
输入:nums = [1] 输出:[]
提示:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
nums
中的每个元素出现 一次 或 两次