leetcode
leetcode 401 ~ 450
找到所有数组中消失的数字

找到所有数组中消失的数字

难度:

标签:

题目描述

给你一个含 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)

代码细节讲解

🦆
在确定一个数字是否消失时,你是怎么考虑数组中存在重复数字的情况的?
在该题解中,通过将原数组转换为集合来处理重复数字的问题。集合是一个不包含重复元素的数据结构,因此即使原数组中有重复的数字,它们在集合中只会被存储一次。这样,当我们遍历从1到n的数字检查它们是否在集合中时,我们实际上是在检查这些数字是否至少出现了一次。不在集合中的数字,即是那些在原数组中完全未出现过的数字,因此被认为是“消失”的数字。
🦆
这种方法对于极大或极小的n表现如何?是否有必要对特殊情况进行优化?
这种方法在时间复杂度上是线性的,即O(n),其中n是数组的长度。空间复杂度也是O(n),因为需要额外的数据结构(集合)来存储数组中的元素。在极大的n值情况下,内存消耗可能成为问题,因为存储大量的数据需要相应大的内存空间。在极小的n值情况下,这个方法效率较高,因为操作的绝对时间和空间成本都非常低。关于优化,对于极大的数据集,可以考虑使用更节省空间的方法,例如原地修改数组(不使用额外的集合)来标记已存在的数字,这种方法可以将空间复杂度降低到O(1)。但这种优化会使得算法的理解和实现变得更复杂,因此是否采用取决于具体的应用场景和性能要求。

相关问题

缺失的第一个正数

给你一个未排序的整数数组 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 中的每个元素出现 一次两次