class Solution {
public:
long long minimalKSum(vector<int>& nums, int k) {
}
};
2195. 向数组中追加 K 个整数
给你一个整数数组 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 <= 1051 <= nums[i], k <= 109原站题解
javascript 解法, 执行用时: 128 ms, 内存消耗: 65 MB, 提交时间: 2023-06-29 10:37:17
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minimalKSum = function(nums, k) {
let set = new Set(nums), sum = (1 + k)*k/ 2, next = k + 1
for(let n of set){
if(n <= k){
while(set.has(next)) next++
sum += next - n, next++
}
}
return sum
};
typescript 解法, 执行用时: 200 ms, 内存消耗: 68.3 MB, 提交时间: 2023-06-29 10:36:23
function minimalKSum(nums: number[], k: number): number {
nums = [...new Set(nums)].sort((a, b) => a - b);
const n: number = nums.length;
let exist: number = 0;
for (let i: number = 0; i < n; i++) {
if (nums[i] <= k) {
k++;
exist += nums[i];
} else {
break;
}
}
return k * (k + 1) / 2 - exist;
};
golang 解法, 执行用时: 124 ms, 内存消耗: 8.8 MB, 提交时间: 2023-06-29 10:35:29
func minimalKSum(nums []int, k int) int64 {
ans := 0
nums = append(nums, 0, math.MaxInt32) // 加入两个哨兵
sort.Ints(nums)
for i := 1; ; i++ {
fill := nums[i] - nums[i-1] - 1 // 可以填充的数字个数
if fill <= 0 { // 没有可以填充的位置
continue
}
if fill >= k { // 填充剩余的 k 个数
return int64(ans + (nums[i-1]*2+1+k)*k/2) // 等差数列求和
}
ans += (nums[i-1] + nums[i]) * fill / 2 // 填充 fill 个数：等差数列求和
k -= fill // 更新剩余要填充的数字个数
}
}
python3 解法, 执行用时: 136 ms, 内存消耗: 30.4 MB, 提交时间: 2023-06-29 10:35:06
class Solution:
def minimalKSum(self, nums: List[int], k: int) -> int:
ans = 0
nums.extend([0, inf]) # 加入两个哨兵
nums.sort()
for x, y in pairwise(nums):
fill = y - x - 1 # 可以填充的数字个数
if fill <= 0: # 没有可以填充的位置
continue
if fill >= k: # 填充剩余的 k 个数
return ans + (x * 2 + 1 + k) * k // 2 # 等差数列求和
ans += (x + y) * fill // 2 # 填充 fill 个数：等差数列求和
k -= fill # 更新剩余要填充的数字个数
java 解法, 执行用时: 19 ms, 内存消耗: 57.8 MB, 提交时间: 2023-06-29 10:34:31
class Solution {
public long minimalKSum(int[] nums, int k) {
Arrays.sort(nums);
long ans = 0, start = 1;
for (int i = 0; i < nums.length && k > 0; i++) {
// 存在未出现的数字
if (start < nums[i]) {
int cnt = (int) (nums[i] - start) > k ? k : (int) (nums[i] - start);
// 不存在的数据累计
ans += (2L * start + cnt - 1) * cnt / 2;
k -= cnt;
}
start = nums[i] + 1;
}
// 不存在的数据累计
if (k > 0) {
ans += (2L * start + k - 1) * k / 2;
}
return ans;
}
}
cpp 解法, 执行用时: 120 ms, 内存消耗: 64.5 MB, 提交时间: 2023-06-29 10:34:06
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;
}
};
python3 解法, 执行用时: 124 ms, 内存消耗: 30.3 MB, 提交时间: 2023-06-29 10:33:40
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
cpp 解法, 执行用时: 132 ms, 内存消耗: 64.6 MB, 提交时间: 2023-06-29 10:29:04
class Solution {
public:
long long minimalKSum(vector<int>& nums, int k) {
// 排序为了去重 也方面k后移
sort(nums.begin(), nums.end());
int n = unique(nums.begin(), nums.end()) - nums.begin(); // 所谓的去重只是把多余的数移到了最后面并没有删除
long long d = 0;
for(int i = 0; i < n; ++i)
{
if(nums[i] <= k)
{
d += nums[i];
++k;
}
}
return (1LL + k) * k / 2 - d;
}
};