leetcode
leetcode 551 ~ 600
错误的集合

错误的集合

难度:

标签:

题目描述

代码结果

运行时间: 59 ms, 内存: 17.0 MB


// 思路:利用Java 8的Stream API来实现相同的逻辑。首先统计每个数字的出现次数。然后找到出现次数为2的数字(重复的)和未出现的数字(丢失的)。
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] count = new int[n + 1];
        Arrays.stream(nums).forEach(num -> count[num]++);
        int duplicate = IntStream.range(1, n + 1).filter(i -> count[i] == 2).findFirst().orElse(-1);
        int missing = IntStream.range(1, n + 1).filter(i -> count[i] == 0).findFirst().orElse(-1);
        return new int[]{duplicate, missing};
    }
}

解释

方法:

本题解使用了两次遍历。第一次遍历数组,利用负号标记法找出重复的元素。具体做法是,遍历到某个元素 nums[i] 时,将 nums[abs(nums[i])-1] 取反。如果发现取反后的值为负数,说明之前已经遍历过该位置,即 abs(nums[i]) 就是重复的元素。第二次遍历数组,找出仍为正数的位置 i,说明 i+1 就是缺失的数字。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在第一次遍历中,你是如何确定一个元素已被重复访问?能否解释一下负号标记法的工作原理?
在第一次遍历中,通过将数组中某个索引位置的值变为其相反数(即负数),来标记该位置对应的数字已经被访问过。具体来说,当遍历到数字 nums[i] 时,将索引 abs(nums[i])-1 的位置的值取反。如果在取反之前,这个位置的值已经是负数,这表明之前已经访问过该位置,因此 abs(nums[i]) 就是重复访问的数字。这种方法通过在原数组上直接修改,避免了额外的空间使用,非常高效。
🦆
为什么在第二次遍历中,未被标记为负数的索引位置i表示i+1是丢失的数字?这种方法是否能确保找到所有类型的缺失数字?
在第二次遍历中,检查哪些索引位置的值仍然是正数。由于之前的遍历中我们将访问过的数字对应的索引位置的值标记为负数,如果某个索引位置 i 的值仍然是正数,这意味着数字 i+1 没有在第一次遍历中被访问过,因此 i+1 就是缺失的数字。这种方法可以确保找到所有类型的缺失数字,只要数组的长度是正确的,即1到n。
🦆
如果输入数组中的数字超出了1到n的范围怎么办?本题解是否还有效?
如果输入数组中的数字超出了1到n的范围,本题解可能不再有效。这是因为算法假设所有数字都在1到n之间,并且使用数字值作为数组索引(通过减1来调整)。超出范围的数字可能导致数组索引越界,或者无法正确标记数字。因此,对于包含超出范围数字的数组,需要先验证所有数字是否在1到n之间,或者使用其他方法来处理这种情况。
🦆
在使用负号标记法时,原数组的值被修改,这种修改是否会影响到算法的其他部分?例如,会不会影响到寻找缺失数字的准确性?
使用负号标记法确实会修改原数组的值,但这种修改是算法设计的一部分,并不会影响到找出重复或缺失数字的准确性。第一次遍历用于标记访问过的数字,而第二次遍历检查哪些位置未被标记(即值仍为正)。只要所有操作都按照设计执行,修改原数组值不会对结果产生不利影响。不过,这种方法的一个缺点是它改变了原数组,这在某些情况下可能是不可接受的。

相关问题

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1:

输入:nums = [1,3,4,2,2]
输出:2

示例 2:

输入:nums = [3,1,3,4,2]
输出:3

示例 3 :

输入:nums = [3,3,3,3,3]
输出:3

 

 

提示:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

 

进阶:

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?