向数组中追加 K 个整数

难度: Medium

给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个未出现在 nums 中的、互不相同 的正整数，并使结果数组的元素和最小。

返回追加到 nums 中的 k 个整数之和。

示例 1：

输入：nums = [1,4,25,10,25], k = 2
输出：5
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。

示例 2：

输入：nums = [5,6], k = 6
输出：25
解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。
nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。
所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁹

Submission

运行时间: 68 ms

内存: 31.2 MB

class Solution:
    def minimalKSum(self, nums: list[int], k: int) -> int:
        ans = k * (k + 1) >> 1
        for num in sorted({*nums}):
            if num <= k:
                k += 1
                ans += k - num
            else:
                break
        return ans

Explain

该题解的核心思路是首先计算如果在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)

class Solution:
    def minimalKSum(self, nums: list[int], k: int) -> int:
        # ans初始化为最小的k个整数的和，即1到k的和
        ans = k * (k + 1) >> 1  # 使用位运算来计算和
        # 遍历排序后的去重nums集合
        for num in sorted({*nums}):
            if num <= k:
                # 如果num小于等于k，需要向后延伸k的范围
                k += 1
                # 更新总和：减去被占据的num，加上新的k值
                ans += k - num
            else:
                # 如果遇到的num大于k，后续的num都不会影响结果，直接终止循环
                break
        return ans

Explore

在题解中，`nums` 数组首先通过 `{*nums}` 这种集合的方式进行去重，因为集合中的元素是唯一的。接下来，对这个去重后的集合进行排序，使用 `sorted` 函数。这种处理方式是为了方便后续的遍历，确保可以按照从小到大的顺序检查每个元素。排序和去重的目的是为了有效地判断哪些是 `nums` 中未出现的最小整数，并且确保添加到 `nums` 中的整数是未出现过且互不相同的。去重保证我们不会重复考虑相同的数字，而排序则允许我们顺序地检查每个数字，简化了逻辑并提高了效率。

这种方法的原理基于寻找并添加未在 `nums` 中出现的最小正整数，以保持整数添加后的总和最小。当元素 `num` 小于等于 `k` 时，意味着 `num` 占据了原本属于 1 到 k 的数字中的一个。因此，为了保持添加的整数数量仍为 k 个，我们需要增加 k 的值（即 `k += 1`），这样可以扩展我们寻找未出现整数的范围。同时，需要从总和中减去 `num` 并加上新的 `k` 值以补偿被占据的位置。这种调整保证了即使 `nums` 中存在 1 到 k 的某些数字，我们仍然能够找到足够数量的未出现的最小正整数来填补，从而保持总和最小。

位运算 `k * (k + 1) >> 1` 用于计算公式 `k * (k + 1) / 2`，即最小的 k 个正整数的和。这种位运算的优势在于执行速度通常比普通的除法运算更快，因为位移运算是底层操作，直接通过移动二进制位来实现除以 2 的效果，从而避免了除法运算的高成本。在大多数现代编译器和处理器上，这种优化在执行效率上有一定的提升。然而，在实际应用中，现代编译器往往能够优化简单的算术表达式，如 `k * (k + 1) / 2`，使得性能差异不大。因此，使用位运算主要是为了代码的简洁性和微小的性能优势。