leetcode
leetcode 1901 ~ 1950
向数组中追加 K 个整数

向数组中追加 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` 数组经过去重和排序后的处理方式是什么?排序和去重对算法的影响是如何体现的?
在题解中,`nums` 数组首先通过 `{*nums}` 这种集合的方式进行去重,因为集合中的元素是唯一的。接下来,对这个去重后的集合进行排序,使用 `sorted` 函数。这种处理方式是为了方便后续的遍历,确保可以按照从小到大的顺序检查每个元素。排序和去重的目的是为了有效地判断哪些是 `nums` 中未出现的最小整数,并且确保添加到 `nums` 中的整数是未出现过且互不相同的。去重保证我们不会重复考虑相同的数字,而排序则允许我们顺序地检查每个数字,简化了逻辑并提高了效率。
🦆
题解中提到,当遇到数组元素`num`小于等于`k`时,会将`k`加1并调整总和。这种处理方法的原理是什么?为什么这样做可以保证找到未在`nums`中出现的最小整数?
这种方法的原理基于寻找并添加未在 `nums` 中出现的最小正整数,以保持整数添加后的总和最小。当元素 `num` 小于等于 `k` 时,意味着 `num` 占据了原本属于 1 到 k 的数字中的一个。因此,为了保持添加的整数数量仍为 k 个,我们需要增加 k 的值(即 `k += 1`),这样可以扩展我们寻找未出现整数的范围。同时,需要从总和中减去 `num` 并加上新的 `k` 值以补偿被占据的位置。这种调整保证了即使 `nums` 中存在 1 到 k 的某些数字,我们仍然能够找到足够数量的未出现的最小正整数来填补,从而保持总和最小。
🦆
题解使用了位运算 `k * (k + 1) >> 1` 来计算最小的k个正整数的和。这种位运算方法的优势是什么?是否存在某些情况下使用普通算术运算相比更为有利?
位运算 `k * (k + 1) >> 1` 用于计算公式 `k * (k + 1) / 2`,即最小的 k 个正整数的和。这种位运算的优势在于执行速度通常比普通的除法运算更快,因为位移运算是底层操作,直接通过移动二进制位来实现除以 2 的效果,从而避免了除法运算的高成本。在大多数现代编译器和处理器上,这种优化在执行效率上有一定的提升。然而,在实际应用中,现代编译器往往能够优化简单的算术表达式,如 `k * (k + 1) / 2`,使得性能差异不大。因此,使用位运算主要是为了代码的简洁性和微小的性能优势。

相关问题