class Solution {
public:
long long kSum(vector<int>& nums, int k) {
}
};
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.length1 <= n <= 105-109 <= nums[i] <= 1091 <= k <= min(2000, 2n)原站题解
rust 解法, 执行用时: 24 ms, 内存消耗: 4.1 MB, 提交时间: 2024-03-09 22:05:12
use std::collections::BinaryHeap;
impl Solution {
pub fn k_sum(mut nums: Vec<i32>, mut k: i32) -> i64 {
let mut sum = 0;
for x in &mut nums {
if *x >= 0 {
sum += *x as i64;
} else {
*x = -*x;
}
}
nums.sort_unstable();
// 注意：为方便实现，改成最大堆，在一开始把 sum 入堆，循环中的加法改成减法
let mut h = BinaryHeap::new();
h.push((sum, 0)); // 空子序列
while k > 1 {
let (s, i) = h.pop().unwrap();
if i < nums.len() {
// 在子序列的末尾添加 nums[i]
h.push((s - nums[i] as i64, i + 1)); // 下一个添加/替换的元素下标为 i+1
if i > 0 { // 替换子序列的末尾元素为 nums[i]
h.push((s - nums[i] as i64 + nums[i - 1] as i64, i + 1));
}
}
k -= 1;
}
h.peek().unwrap().0
}
}
golang 解法, 执行用时: 135 ms, 内存消耗: 8.8 MB, 提交时间: 2024-03-09 22:04:56
func kSum(nums []int, k int) int64 {
n := len(nums)
sum := 0
for i, x := range nums {
if x >= 0 {
sum += x
} else {
nums[i] = -x
}
}
slices.Sort(nums)
h := hp{{0, 0}} // 空子序列
for ; k > 1; k-- {
p := heap.Pop(&h).(pair)
i := p.i
if i < n {
// 在子序列的末尾添加 nums[i]
heap.Push(&h, pair{p.sum + nums[i], i + 1}) // 下一个添加/替换的元素下标为 i+1
if i > 0 { // 替换子序列的末尾元素为 nums[i]
heap.Push(&h, pair{p.sum + nums[i] - nums[i-1], i + 1})
}
}
}
return int64(sum - h[0].sum)
}
type pair struct{ sum, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].sum < h[j].sum }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
java 解法, 执行用时: 66 ms, 内存消耗: 55.1 MB, 提交时间: 2024-03-09 22:04:40
class Solution {
public long kSum(int[] nums, int k) {
long sum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= 0) {
sum += nums[i];
} else {
nums[i] = -nums[i];
}
}
Arrays.sort(nums);
PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(a.getKey(), b.getKey()));
pq.offer(new Pair<>(0L, 0)); // 空子序列
while (--k > 0) {
Pair<Long, Integer> p = pq.poll();
long s = p.getKey();
int i = p.getValue();
if (i < nums.length) {
// 在子序列的末尾添加 nums[i]
pq.offer(new Pair<>(s + nums[i], i + 1)); // 下一个添加/替换的元素下标为 i+1
if (i > 0) { // 替换子序列的末尾元素为 nums[i]
pq.offer(new Pair<>(s + nums[i] - nums[i - 1], i + 1));
}
}
}
return sum - pq.peek().getKey();
}
}
python3 解法, 执行用时: 1736 ms, 内存消耗: 33 MB, 提交时间: 2022-10-19 15:06:31
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
sum = tot = 0
for i, x in enumerate(nums):
if x >= 0:
sum += x
tot += x
else:
tot -= x
nums[i] = -x
nums.sort()
def count(limit: int) -> int:
cnt = 0
def f(i: int, s: int) -> None:
nonlocal cnt
if i == len(nums) or cnt >= k - 1 or s + nums[i] > limit:
return
cnt += 1
f(i + 1, s + nums[i]) # 选
f(i + 1, s) # 不选
f(0, 0)
return cnt
return sum - bisect_left(range(tot), k - 1, key=count)
python3 解法, 执行用时: 228 ms, 内存消耗: 26.4 MB, 提交时间: 2022-10-19 15:04:44
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
sum = 0
for i, x in enumerate(nums):
if x >= 0: sum += x
else: nums[i] = -x
nums.sort()
h = [(-sum, 0)] # 取负号变成最大堆
for _ in range(k - 1):
s, i = heappop(h)
if i < len(nums):
heappush(h, (s + nums[i], i + 1)) # 保留 nums[i-1]
if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1)) # 不保留 nums[i-1]
return -h[0][0]