How does the greedy approach work in 'Append K Integers With Minimal Sum'?

The greedy approach works by always selecting the smallest integers that are missing from nums, ensuring the sum of appended integers is minimized.

What is the time complexity of the solution?

The time complexity is O(n + k), where n is the length of nums and k is the number of integers to append.

How do you efficiently track which integers are missing from nums?

You can use a set to store the elements of nums, allowing for quick lookup to determine missing integers.

Can this problem be solved using sorting?

Sorting can be used, but a greedy approach with set-based lookups is more efficient for minimizing the sum.

What is the main pattern used in this problem?

The main pattern is greedy choice with invariant validation, ensuring the minimum sum by always choosing the smallest missing integers.

#2195

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

向数组中追加 K 个整数

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个未出现在 nums 中的、互不相同的正整数，并使结果数组的元素和最小。返回追加到 nums 中的 k 个整数之和。示例 1：输入： nums = [1,4,25,10,25], k = 2 输出： 5…

数组数学贪心排序

题目描述

给你一个整数数组 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⁹

lightbulb

解题思路

方法一：排序 + 贪心 + 数学

我们不妨向数组中加入两个哨兵节点，分别为 $0$ 和 $2 \times 10^9$ 。

然后我们对数组进行排序，那么对于数组中的任意两个相邻的元素 $a$ 和 $b$ ，区间 $[a+1, b-1]$ 中的整数都是未出现在数组中的，我们可以将这些整数加入到数组中。

因此，我们从小到大遍历数组中的相邻元素对 $(a, b)$ ，对于每个相邻元素对，我们计算区间 $[a+1, b-1]$ 中的整数个数 $m$ ，那么这 $m$ 个整数的和为 $\frac{m \times (a+1 + a+m)}{2}$ ，我们将这个和累加到答案中，并将 $k$ 减去 $m$ 。如果 $k$ 减到 $0$ ，我们就可以停止遍历了，返回答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums.extend([0, 2 * 10**9])
        nums.sort()
        ans = 0
        for a, b in pairwise(nums):
            m = max(0, min(k, b - a - 1))
            ans += (a + 1 + a + m) * m // 2
            k -= m
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + k) where n is the length of nums and k is the number of integers to be appended. Space complexity is O(n) due to the storage of nums in a set for fast lookup.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands how to apply greedy strategies to minimize sums.
question_mark
Evaluate the candidate's ability to optimize using set-based lookups.
question_mark
Look for knowledge of efficient ways to append elements while minimizing time complexity.

warning

常见陷阱

外企场景

error
Not considering the uniqueness constraint of the appended integers.
error
Incorrectly calculating the sum, failing to track only the sum of the appended numbers.
error
Inefficient lookups or appending methods that degrade performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Appending a larger number of integers, testing how the algorithm scales with larger k.
arrow_right_alt
Variation where nums already contains most of the integers, requiring careful selection of missing integers.
arrow_right_alt
Approach using sorting or other methods instead of greedy choice to check optimization.

help

常见问题

外企场景

继续练习

#2607 使子数组元素和相等 #1686 石子游戏 VI #1648 销售价值减少的颜色球