错误的集合
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在第一次遍历中,你是如何确定一个元素已被重复访问?能否解释一下负号标记法的工作原理?
▷🦆
为什么在第二次遍历中,未被标记为负数的索引位置i表示i+1是丢失的数字?这种方法是否能确保找到所有类型的缺失数字?
▷🦆
如果输入数组中的数字超出了1到n的范围怎么办?本题解是否还有效?
▷🦆
在使用负号标记法时,原数组的值被修改,这种修改是否会影响到算法的其他部分?例如,会不会影响到寻找缺失数字的准确性?
▷相关问题
寻找重复数
给定一个包含 n + 1
个整数的数组 nums
,其数字都在 [1, n]
范围内(包括 1
和 n
),可知至少存在一个重复的整数。
假设 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)
的解决方案吗?