2386. 找出数组的第 K 大和 (每日一难phase2-day2)

2386. 找出数组的第 K 大和

给你一个整数数组 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 <= 1e5
-1e9 <= nums[i] <= 1e9
1 <= k <= min(2000, 2n)

解析：

• 最大的数一定是所有正数相加
• 此大的数一定是拿最大的数减去一个正数或者加上一个负数（到底是减正数，还是加负数，当然谁的绝对值小减谁），本质上就是减去一个绝对值较小的数。因此，可以将所有的负数变成正数，统一操作为减去一个正数。
• 求第k大数可以使用堆求得，此时需要将所有子序列列举出来（可以考虑使用dfs求所有子序列的情况，针对每个元素取或者不取）

代码：

class Solution {
public:
    // 将所有子序列找出，优先队列求第k大
    long long kSum(vector<int>& nums, int k) {
        long long ans;
        long long sum=0;
        // 找出最大值，并将元素取绝对值
        for(auto &a : nums){
            if(a>=0) 
                sum+=a; 
            else 
                a = -a;
        }
        // 按照绝对值从小到大排序
        sort(nums.begin(),nums.end());
        priority_queue<pair<long long ,int>> pq;
        // 大根堆放入最大元素，及序号
        pq.push({sum,0});
        while(--k){
            auto [a,b] = pq.top();
            pq.pop();
            if(b<nums.size()){
            	// 舍弃当前元素，保留前一个元素
                pq.push({a-nums[b],b+1});
                // 舍弃当前元素，不保留前一个元素，把之前减去加回来
                if(b) pq.push({a-nums[b]+nums[b-1],b+1});
            }
        }
        // k-1个最大已经排除，堆顶为第k
        return pq.top().first;
    }
};
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
28
29
30
31
32

代码参考：视频讲解