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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 堆
/// 1. 计算所有非负元素的和. 得到最大子序列和: sum = sum(nums[i]) (nums[i]>0);
/// 2. 第k大子序列和为: k_max_sum = sum - k_min_abs_sum (第k-1小绝对值子序列和);
/// 3. 为找到第k小绝对值子序列(后面的子序列都是指绝对值序列)和k_min_abs_sum, 一般需要进行如下操作:
/// a. 找到一种不重不漏生成所有子序列组合的方法;
/// b. 计算绝对值子序列的和;
/// c. 从小到大选择第k小的即可;
/// 4. 上述算法存在一些问题:
/// a. 如何不重不漏的生成子序列?
/// b. 当n很大时, 生成所有子序列组合数将是O(n!)级别的, 是一个很大的消耗;
/// 而目标只需要得到第k小的组合, 如何改进?
/// c. 如何快速找到第k小的子序列和?
/// 5. 对于上述问题, 可进行如下思考:
/// a. 子序列有部分元素组成, 如要生成和小的和子序列, 须尽量选择绝对值小的元素组成的子序列,
/// 为此可先将nums按绝对值从小->大排序, 从小到大依次选择;
/// b. 设排序后的元素分别为: n[0], n[1], n[2],.., n[i],..,
/// 有: n[0] < n[1] < .. < n[i] < ..,
/// 依次按 n[0], n[1], .., n[i]顺序选择元素来生成新的子序列;
/// c. 对于每次当前选择的元素n[i], 有两种方式来生成新的和次大的一些子序列:
/// - 增加n[i]到子序列中;
/// - 替换n[i-1];
/// 设s: 表示选择n[i]前的子序列和, 则上述两种操作可表示为:
/// - s + n[i]
/// - s - n[i-1] + n[i]
/// 设选择n[i]前, s为第j小的子序列和,
/// 则, s + n[i], s-n[i-1]+n[i], 的子序列和顺序一定不大于2j
/// d. 为了保证能快速找到j+1小的子序列和, 可将这些新子序列和用一个最小堆min_heap缓存起来;
/// 初始时将(s=0, i=0)入堆, s表示当前子序列和, i表示下一个要取的元素n[i]的下标;
/// 每次进行如下操作:
/// a1. 弹出堆顶元素(s, i);
/// a2. 按照c中方式, 依次向堆中压入(s + n[i], i+1), (s-n[i-1]+n[i], i+1);
/// 设: 第j次取出堆顶元素(s, i), 则由于每次都从堆中弹出一个元素, 而压入2个元素,
/// 则第j次,堆中剩余的元素数为j个, 堆中已经弹出的元素为j, 而每次更新子的子序列和
/// 不会大于第2j个最小子序列和, 因此第j+1小子序列和必定在堆中;
/// 而由于小顶堆的性质, 此时堆顶必定为下一个最小和的子序列;
/// e. 由此, 循环k-1次, 从堆顶弹出的s为第k-1小子序列和;
/// d. 最终结果为: sum - s[k-1];
/// f. 题目中将堆换成大顶堆, 初始时将(sum, 0)入堆, 每次反过来计算sum-s
/// 最小子序列生成顺序:
/// [] [0] [1] [2] [3]
/// 00000000 00000001 00000010 00000100 00001000
/// [2,3]
/// 00001100
/// [1,2] [1,3]
/// 00000110 00001010
/// [1,2,3]
/// 00001110
/// [0,1] [0,2] [0,3]
/// 00000011 00000101 00001001
/// [0,2,3]
/// 00001101
/// [0,1,2] [0,1,3]
/// 00000111 00001011
/// [0,1,2,3]
/// 00001111
pub fn k_sum(nums: Vec<i32>, k: i32) -> i64 {
use std::collections::BinaryHeap;
// 计算所有非负元素组成的最大子序列和
let mut sum = nums
.iter()
.map(|&n| n as i64)
.filter(|&n| n > 0)
.sum::<i64>();
let mut nums = nums;
// 将nums中的所有元素按绝对值从小到大排序
nums.sort_by(|&a, &b| a.abs().cmp(&b.abs()));
// 设置大顶堆()
let mut top_k_sums = BinaryHeap::<(i64, usize)>::with_capacity(k as usize);
// 将最大序列和初始入堆
top_k_sums.push((sum as i64, 0));
// 依次取出1..k的大的子序列和
for _ in 1..(k as usize) {
// 弹出堆顶元素
match top_k_sums.pop() {
Some((sum, i)) => {
if i < nums.len() {
// 最小子序列和中包含nums[i]和nums[i-1]
top_k_sums.push(((sum - (nums[i].abs() as i64)), i + 1));
if i > 0 {
// 最小子序列和中包含nums[i], 不包含nums[i-1]
top_k_sums.push((
(sum - ((nums[i].abs() as i64) - (nums[i - 1].abs() as i64))),
i + 1,
));
}
}
}
_ => {}
}
}
// 前面的第k-1大序列和都弹出了
top_k_sums.pop().unwrap().0
}
}
// @lc code=end
|