5.2 KiB
2389. 和有限的最长子序列
description：
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
代码：
fn main() {
let mut nums = vec![4, 5, 2, 1];
let queries = vec![3,10,21];
// let mut nums = vec![2, 3, 4, 5];
// let queries = vec![1];
let res = answer_queries(&mut nums, &queries);
for i in res {
println!(" {} ", i);
}
let queries = vec![0,1,3,7,12];
let idx = queries.binary_search_by(|&x| x.cmp(&6))
.map_or_else(|j| j, |j| j + 1);
println!("idx is {} ", idx-1);
let idx:i32 = queries.binary_search_by(|&x| x.cmp(&1))
.map_or_else(|j| j, |j| j + 1) as i32;
println!("idx is {} ", idx);
}
fn answer_queries(nums:&mut [i32], queries:&[i32]) -> Vec<i32>{
let n = nums.len();
let m = queries.len();
nums.sort_unstable();
let mut p = vec![0; n+1];
for i in 0..n {
p[i+1] = p[i] + nums[i];
}
let mut answer:Vec<i32> = Vec::with_capacity(m);
answer.resize(m, 0); // 使用push就不要使用resize了。
// let mut answer = vec![0; m]; // 2
for i in 0..m {
// let idx = match p.binary_search_by(|&x| x.cmp(&queries[i])) {
// Ok(j) => j+1,
// Err(j) => j,
// };
let idx = p.binary_search_by(|&x| x.cmp(&queries[i]))
.map_or_else(|j| j, |j| j + 1);
answer[i] = (idx - 1) as i32;
// answer.push((idx - 1) as i32); //resize了就不要用这个
}
answer
}
图：
sort_unstable 和 sort 方法都可以用于排序，区别在于它们的稳定性和性能。
sort_unstable不保证相等元素的相对顺序，但由于它不需要维护元素间的稳定性，因此通常比sort更快。sort保证相等元素的相对顺序，它使用的是快排或归并排序等稳定排序算法。由于需要维护元素间的稳定性，因此通常比sort_unstable慢。
在实际使用中，如果对排序结果的稳定性没有特别要求，可以优先考虑使用 sort_unstable 来提高性能。如果需要保证相等元素的相对顺序，再使用 sort。
-
使用
with_capacity方法预分配内存，避免反复分配和释放内存的开销。但是未初始化len为 0；answer.resize(m, 0)的意思是将answer的长度调整为m，并将多余的位置（如果有）设置为默认值0。如果answer的长度已经大于等于m，则不做任何操作。 -
C++ upper_bound 与 rust binary_search_by 区别：
upper_bound 的作用是找到 p 中第一个大于等于 queries[i] 的数的下标。binary_search_by 函数返回的是找到元素在数组中的下标，如果找到了就直接返回下标 j，否则返回不大于 queries[i] 的最大元素的下标 j。由于 p 数组中的元素是不递减的，所以如果要插入一个比最后一个元素还要大的元素，需要插入到 n 的位置，即数组的最后一个位置。因此，对于 Err(j) 的情况，插入的位置就是 j。而对于 Ok(j) 的情况，插入的位置应该是 j+1。
在 C++ 中使用 upper_bound 函数来查找大于 queries[i] 的第一个元素的下标，这个函数返回的是一个迭代器，指向的是第一个大于 queries[i] 的元素，所以需要再将其前移一位，即 upper_bound(f.begin(), f.end(), queries[i]) - f.begin() - 1。而在 Rust 中使用 binary_search_by 函数来查找大于等于 queries[i] 的第一个元素的下标，这个函数返回的是一个 Result<usize, usize> 类型的值，表示查找的结果。如果查找成功，则返回查找到的元素在数组中的下标；如果查找失败，则返回一个在哪个位置插入元素可以保持数组的有序性的下标。由于 Rust 中数组的下标是从 0 开始的，所以需要将 j 加 1，即 (j+1)-1，得到插入的位置。
for i in 0..m {
let idx = p.binary_search_by(|&x| x.cmp(&queries[i]))
.map_or_else(|j| j, |j| j + 1);
answer[i] = (idx - 1) as i32;
}
这段代码的意思是在p数组中二分查找queries[i]，如果找到了，则返回该元素在数组中的索引j，并加一赋值给idx；如果没找到，则返回比queries[i]大的元素在数组中的索引j，并直接赋值给idx。最后将(idx - 1)转换成i32类型并赋值给answer[i]。
如果结果是Ok，则执行第一个闭包，即返回Ok中的值j；如果结果是Err，则执行第二个闭包，即返回Err中的值j。
binary_search_by 返回的idx为插入（新增）到此位置不会影响函数顺序的下标，idx-1就是他可以替换的值得下标。