Medium

题目描述

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

返回追加的 k 个整数的和。

示例 1：

输入：nums = [1,4,25,10,25], k = 2
输出：5
解释：不出现在 nums 中的两个互不相同的正整数是 2 和 3 。
nums 追加后的和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，是所有情况中的最小值。
追加的两个整数的和是 2 + 3 = 5 ，所以返回 5 。

示例 2：

输入：nums = [5,6], k = 6
输出：25
解释：不出现在 nums 中的六个互不相同的正整数是 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^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^8

解题思路

解题思路

为了使追加的 k 个整数和最小，我们应该选择最小的 k 个未在数组中出现的正整数。

核心思想：

  1. 从1开始，逐步选择最小的未出现的正整数
  2. 使用数学公式 1+2+...+n = n*(n+1)/2 来快速计算连续正整数的和
  3. 遇到数组中已存在的数字时，需要跳过并选择更大的数字

算法步骤：

  1. 对数组去重并排序，便于处理
  2. 初始化答案为前k个正整数的和：k*(k+1)/2
  3. 遍历排序后的数组，对于每个在范围[1, k+已跳过数字个数]内的数字：
    • 将其从答案中减去（因为不能选择）
    • 将k+已跳过数字个数+1加到答案中（选择下一个可用的数字）
    • 更新已跳过的数字个数

优化点：

  • 使用set去重可以避免重复处理相同数字
  • 只需要考虑小于等于k+当前跳过数量的数字，因为更大的数字不会影响我们选择的前k小数字

这种方法的时间复杂度主要由排序决定，空间复杂度用于存储去重后的数组。

代码实现

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        set<int> uniqueNums(nums.begin(), nums.end());
        vector<int> sortedNums(uniqueNums.begin(), uniqueNums.end());
        
        long long result = (long long)k * (k + 1) / 2;
        int skipped = 0;
        
        for (int num : sortedNums) {
            if (num <= k + skipped) {
                result = result - num + (k + skipped + 1);
                skipped++;
            } else {
                break;
            }
        }
        
        return result;
    }
};

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        unique_nums = sorted(set(nums))
        
        result = k * (k + 1) // 2
        skipped = 0
        
        for num in unique_nums:
            if num <= k + skipped:
                result = result - num + (k + skipped + 1)
                skipped += 1
            else:
                break
                
        return result

public class Solution {
    public long MinimalKSum(int[] nums, int k) {
        var uniqueNums = new SortedSet<int>(nums);
        
        long result = (long)k * (k + 1) / 2;
        int skipped = 0;
        
        foreach (int num in uniqueNums) {
            if (num <= k + skipped) {
                result = result - num + (k + skipped + 1);
                skipped++;
            } else {
                break;
            }
        }
        
        return result;
    }
}

var minimalKSum = function(nums, k) {
    const uniqueNums = [...new Set(nums)].sort((a, b) => a - b);
    
    let result = k * (k + 1) / 2;
    let skipped = 0;
    
    for (const num of uniqueNums) {
        if (num <= k + skipped) {
            result = result - num + (k + skipped + 1);
            skipped++;
        } else {
            break;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，其中n是数组长度
空间复杂度O(n)用于存储去重后的数组

相关题目