2386. 数组的第K大元素和

Hard

题目描述

给你一个整数数组 nums 和一个正整数 k。你可以选择数组的任意子序列，并将其所有元素求和。

我们将数组的 第K大元素和 定义为可以获得的第 k 大的子序列和（不一定不同）。

返回数组的第K大元素和。

子序列 是可以通过删除某些元素或不删除元素而不改变其余元素顺序，从另一个数组派生出来的数组。

注意空的子序列被认为其和为 0。

示例 1：

输入：nums = [2,4,-2], k = 5
输出：2
解释：我们可以获得的所有可能的子序列和按降序排列如下：
6, 4, 4, 2, 2, 0, 0, -2。
数组的第5大元素和是2。

示例 2：

输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第16大元素和是10。

提示：

n == nums.length
1 <= n <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= min(2000, 2^n)

解题思路

这是一道经典的第K大问题，核心思路是从最大和开始，逐步生成次大和。

分析思路：

最大的子序列和是所有非负数的和
从任意一个子序列和，我们可以通过两种操作得到更小的和：
- 如果当前包含某个正数，移除它
- 如果当前不包含某个负数，添加它

算法步骤：

将数组分为正数和负数两部分，正数按降序排列，负数按绝对值升序排列
计算所有正数的和作为初始最大和
使用优先队列（最大堆）维护候选和，每次取出最大的和
对于每个取出的和，生成两个新的候选和：
- 移除一个正数（如果有的话）
- 添加一个负数（如果有的话）
重复k-1次得到第k大和

优化要点：

使用状态压缩，用索引表示当前操作到哪个位置
避免重复状态的生成

代码实现

class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long maxSum = 0;
        vector<int> abs_nums;
        
        for (int num : nums) {
            if (num >= 0) {
                maxSum += num;
            }
            abs_nums.push_back(abs(num));
        }
        
        sort(abs_nums.begin(), abs_nums.end());
        
        priority_queue<pair<long long, int>> pq;
        pq.push({maxSum, 0});
        
        for (int i = 1; i < k; i++) {
            auto [sum, idx] = pq.top();
            pq.pop();
            
            if (idx < abs_nums.size()) {
                pq.push({sum - abs_nums[idx], idx + 1});
                if (idx > 0) {
                    pq.push({sum - abs_nums[idx] + abs_nums[idx - 1], idx + 1});
                }
            }
        }
        
        return pq.top().first;
    }
};

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        max_sum = sum(x for x in nums if x >= 0)
        abs_nums = sorted([abs(x) for x in nums])
        
        heap = [(-max_sum, 0)]
        
        for _ in range(k - 1):
            neg_sum, idx = heappop(heap)
            sum_val = -neg_sum
            
            if idx < len(abs_nums):
                heappush(heap, (-(sum_val - abs_nums[idx]), idx + 1))
                if idx > 0:
                    heappush(heap, (-(sum_val - abs_nums[idx] + abs_nums[idx - 1]), idx + 1))
        
        return -heap[0][0]

public class Solution {
    public long KSum(int[] nums, int k) {
        long maxSum = 0;
        var absNums = new List<int>();
        
        foreach (int num in nums) {
            if (num >= 0) {
                maxSum += num;
            }
            absNums.Add(Math.Abs(num));
        }
        
        absNums.Sort();
        
        var pq = new PriorityQueue<(long sum, int idx), long>(
            Comparer<long>.Create((a, b) => b.CompareTo(a))
        );
        pq.Enqueue((maxSum, 0), maxSum);
        
        for (int i = 1; i < k; i++) {
            var (sum, idx) = pq.Dequeue();
            
            if (idx < absNums.Count) {
                pq.Enqueue((sum - absNums[idx], idx + 1), sum - absNums[idx]);
                if (idx > 0) {
                    long newSum = sum - absNums[idx] + absNums[idx - 1];
                    pq.Enqueue((newSum, idx + 1), newSum);
                }
            }
        }
        
        return pq.Peek().sum;
    }
}

var kSum = function(nums, k) {
    let maxSum = 0;
    const absNums = [];
    
    for (const num of nums) {
        if (num >= 0) {
            maxSum += num;
        }
        absNums.push(Math.abs(num));
    }
    
    absNums.sort((a, b) => a - b);
    
    const pq = new MaxPriorityQueue({ priority: x => x[0] });
    pq.enqueue([maxSum, 0]);
    
    for (let i = 1; i < k; i++) {
        const [sum, idx] = pq.dequeue().element;
        
        if (idx < absNums.length) {
            pq.enqueue([sum - absNums[idx], idx + 1]);
            if (idx > 0) {
                pq.enqueue([sum - absNums[idx] + absNums[idx - 1], idx + 1]);
            }
        }
    }
    
    return pq.front().element[0];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(n log n + k log k)
空间复杂度	O(n + k)

其中 n 是数组长度。时间复杂度主要由排序 O(n log n) 和堆操作 O(k log k) 组成。空间复杂度主要用于存储绝对值数组和优先队列。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析