前言:
现在各位老铁们对“非负数包含什么数值”大致比较关怀,各位老铁们都想要剖析一些“非负数包含什么数值”的相关知识。那么小编在网上网罗了一些有关“非负数包含什么数值””的相关资讯,希望同学们能喜欢,朋友们快快来学习一下吧!2022-06-16:给定一个数组arr,含有n个数字,都是非负数,
给定一个正数k,
返回所有子序列中,累加和最小的前k个子序列累加和。
假设K不大,怎么算最快?
来自亚马逊。
答案2022-06-16:
排序,小根堆。
代码用rust编写。代码如下:
fn main() { let mut nums: Vec<i32> = vec![6, 19, 3, 8, 29]; let ans = top_min_sum2(&mut nums, 3); println!("ans = {:?}", ans);}fn top_min_sum2(arr: &mut Vec<i32>, k: i32) -> Vec<i32> { arr.sort(); // (最右的下标,集合的累加和) let mut heap: Vec<Vec<i32>> = vec![]; heap.push(vec![0, arr[0]]); let mut ans: Vec<i32> = vec![]; for _ in 0..k { ans.push(0); } // ans[0] = 0 // 0 1 2 k-1 // k个! for i in 1..k { heap.sort_by(|a, b| b[1].cmp(&a[1])); let cur = heap.pop().unwrap(); // (7, 100) // 左 :8, 100 - arr[7] + arr[8] // 右 :8, 100 + arr[8] let last = cur[0]; let sum = cur[1]; ans[i as usize] = sum; if last + 1 < arr.len() as i32 { heap.push(vec![ last + 1, sum - arr[last as usize] + arr[(last + 1) as usize], ]); heap.push(vec![last + 1, sum + arr[(last + 1) as usize]]); } } return ans;}
执行结果如下:
***
[左神java代码]()
标签: #非负数包含什么数值