2195-向数组中追加 K 个整数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个整数数组 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 <= 105
  • 1 <= nums[i], k <= 109

方法一：排序

思路与算法

首先可以明确的是：最优的方法一定是从 1 开始，依次往数组 nums 中添加未出现过的正整数，直到添加了 k 个正整数为止。

因此，我们首先对数组 nums 进行升序排序，随后在数组的最前面添加元素 0，最后面添加元素 \infty。这样一来，我们从 nums 的第一个元素（首元素为第 0 个元素）开始遍历。当遍历到 nums}[i] 时，如果 nums}[i-1] + 1 < \textit{nums}[i]，那么我们就可以在 [\textit{nums}[i-1] + 1, \textit{nums}[i] - 1] 的范围内添加正整数，总计 nums}[i] - \textit{nums}[i-1] - 1 个。如果这个值小于 k，那么我们需要添加该范围内的全部正整数，并将 k 减去这个值；否则我们只需要添加从 nums}[i] + 1 开始的最小 k 个正整数即可。此时，添加到数组中的所有正整数之和，即为 1 + 2 + \cdots + (\textit{nums}[i-1] + k) 减去所有已完成遍历的元素之和。

细节

本题中有两个细节需要注意：

  • 由于数组 nums 中的元素和 k 均不超过 10^9，因此添加的正整数一定不会超过 2 \times 10^9，即我们可以用 2 \times 10^9 + 1 代替 \infty。

  • 由于数组 nums 中会出现重复的元素，因此在维护「所有已完成遍历的元素之和」时，不能计入重复的元素。即当 nums}[i-1] = \textit{nums}[i] 时不能计入 nums}[i]。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        nums.push_back(0);
        nums.push_back(int(2e9) + 1);
        sort(nums.begin(), nums.end());

        long long presum = 0, ans = 0;
        for (int i = 1; i < nums.size(); ++i) {
            int offer = nums[i] - nums[i - 1] - 1;
            if (offer > 0) {
                if (offer < k) {
                    k -= offer;
                }
                else {
                    ans = static_cast<long long>(nums[i - 1] + k + 1) * (nums[i - 1] + k) / 2 - presum;
                    break;
                }
            }
            if (nums[i] != nums[i - 1]) {
                presum += nums[i];
            }
        }

        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums.extend([0, int(2e9) + 1])
        nums.sort()

        presum = 0
        ans = 0
        for i in range(1, len(nums)):
            offer = nums[i] - nums[i - 1] - 1
            if offer > 0:
                if offer < k:
                    k -= offer
                else:
                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum
                    break
            if nums[i] != nums[i - 1]:
                presum += nums[i]
        
        return ans

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 nums 的长度，即为排序需要的时间。

  • 空间复杂度：O(\log n)，即为排序需要使用的栈空间。

 Comments
On this page
2195-向数组中追加 K 个整数