向数组中追加 K 个整数
难度:
标签:
题目描述
代码结果
运行时间: 68 ms, 内存: 31.2 MB
/*
* 思路:
* 使用Java Stream API实现与上述思路相同的逻辑。
* 通过生成一个无限的IntStream,过滤掉在nums中出现的数,
* 然后取前k个数,并计算它们的和。
*/
import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public int minimalSum(int[] nums, int k) {
Set<Integer> numSet = Arrays.stream(nums).boxed().collect(Collectors.toSet());
return IntStream.iterate(1, n -> n + 1)
.filter(n -> !numSet.contains(n))
.limit(k)
.sum();
}
}
解释
方法:
该题解的核心思路是首先计算如果在nums中没有任何数存在的情况下,最小的k个正整数(1到k)的和。然后,为了保证添加的数都是未在nums中出现过的且互不相同的正整数,算法会遍历经过去重和排序后的nums数组。对于每个元素num,如果num小于或等于k,这意味着num占据了原本属于1到k中的某个数的位置,因此我们需要向后延伸k的范围,并调整总和以补偿这种占据。具体操作是k加1(因为需要额外的一个数来保持数量为k),并从总和中减去num,加上新的k值。这个过程一直持续到遇到的num大于当前的k值,因此后面的数不会影响1到k的范围内的数的选择。
时间复杂度:
O(m log m)
空间复杂度:
O(m)
代码细节讲解
🦆
在题解中,`nums` 数组经过去重和排序后的处理方式是什么?排序和去重对算法的影响是如何体现的?
▷🦆
题解中提到,当遇到数组元素`num`小于等于`k`时,会将`k`加1并调整总和。这种处理方法的原理是什么?为什么这样做可以保证找到未在`nums`中出现的最小整数?
▷🦆
题解使用了位运算 `k * (k + 1) >> 1` 来计算最小的k个正整数的和。这种位运算方法的优势是什么?是否存在某些情况下使用普通算术运算相比更为有利?
▷