1.7. 找出数组的第 K 大和原理及C++实现

题目

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。
注意：空子序列的和视作 0 。
nums的长度为[1,100000]，nums[i]取值[-10^9,10^9]。
1 <= k <= min(2000, 2n)

时间复杂度

O(nlogn)+O(klogn)。预处理，排序的时间复杂度为O(nlogn);出队入队的时间复杂度为O(klogk)

nums[i]全部是正数，求k大组合和

先按升序排序。用状态压缩来表示系列，如果选取了nums[0]，则mask |= 1;如果选取了nums[1]，则mask|=2;如果选取了nums[2],则mask|=4；如果选取了nums[3],则mask|=8。

规律：
规律一：上表中任何数据都小或等于同行前一列。第0列转化一个数，其它列转化两个数。第i列转化方式：a，从系列中删除nums[i]。b，从序列中删除nums[i]，增加nums[i-1]。nums[i]大于等于0，所以a方式一定变小或不变；nums[i]>=nums[i-1]，b方式也变小或不变。
规律二：第i（从0开始）列，从低到高，第i-1位为0，比i-1高的位全位1，比i-1位低的枚举各种可能。前面是n1个1,中间是0，最后是n2位有2^n2种可能。下一列是n1-1个1，中间是0，最后有n2+1位，2^(n2+1)种可能。去掉重复的首位尾位，就是10变成00和01，分别对应第一点的a,b两种方式。
规律三：第i列一定存在nums[i]，因为之前依次删除nums[0]…nums[i-1]，没删除过nums[i]。由规律二可以得出一定不存在nums[i-1]。

推论：
由规律一可得，第k大一定是前k-1的a方式或b方式。也就是队列的中元素数是O(k)，队列中只需要存在前k-1大的a方式和b方式。

负数处理

假定存在负数，其绝对值为x。任意一个不包括-x的子系列，其和为s，则选取x，其和为s-x。把-x变成x，则不选取x和选取x，分别为s,s+x。我把-x转成x，再对任意序列和减去-x。就等价了。通俗的说，选则-x，变成不选；不选，变成选择x。
负数转为正数之前，计算最大值：所有非负数之和。
负数转为正数之后，计算最大值：所有非负数之和+所有负数的绝对值-所有负数的绝对值=所有非负数之和。

核心代码

class Solution {
public:
  long long kSum(vector& nums, int k) {
    long long llMax = 0;
    for (auto& n : nums)
    {
      if (n < 0)
      {
        n *= -1;
      }
      else
      {
        llMax += n;
      }
    }
    sort(nums.begin(), nums.end());
    std::priority_queue> que;
    que.emplace(llMax, 0);
    while (--k)
    {
      auto [llSum, i] = que.top();
      que.pop();
      if (i >= nums.size())
      {
        continue;
      }
      que.emplace(llSum - nums[i], i + 1);
      if (i > 0)
      {
        que.emplace(llSum - nums[i]+nums[i-1], i + 1);
      }
    }
    return que.top().first;
  }
};

测试用例

int main()

{

         vector<int> nums = { 2,4,-2 };

         //vector nums = { 6, 3, 6, 1, 0, 8, 0, 6, 6 };

         //vector nums = { 1,0,0,2,0 };

         auto res = Solution().kSum(nums, 5);

CConsole::Out(res);

}

其它

视频课程

基础算法的C++实现课程，请点击下面的CSDN学院的链接。

https://edu.csdn.net/course/detail/38771

我还做了其它课程，比如：C++入职培训，C#入职培训。

https://edu.csdn.net/lecturer/6176

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

相关下载

如果你时间宝贵，只想看精华，请到CSDN下载频道下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653