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。

只有一个数
1(二进制1)	0(0)
只有两个数
3(11)	2(10)	0(00)
		1(01)
只有三个数
7(111)	6(110)	4(100)	0(000)
			2(010)
		5(101)	1(001)
			3(011)
只有4个数
15(1111)	1110	1100	1000	0000
				0100
			1010	0010
				0110
		1101	1001	0001
				0101
			1011	0011
				0111

规律：
规律一：上表中任何数据都小或等于同行前一列。第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<int>& 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<std::pair<long long, int>> 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<int> nums = { 6, 3, 6, 1, 0, 8, 0, 6, 6 };

         //vector<int> nums = { 1,0,0,2,0 };

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

CConsole::Out(res);

}

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653