以下是 LeetCode 3911 的 Rust 实现方法名已按要求使用 kth_remaining_integerrustimpl Solution {pub fn kth_remaining_integer(nums: Veci32, queries: VecVeci32) - Veci32 {// 预处理提取所有偶数的下标和值严格递增let mut even_idx: Vecusize Vec::new();let mut even_val: Veci32 Vec::new();for (i, x) in nums.iter().enumerate() {if x % 2 0 {even_idx.push(i);even_val.push(x);}}let m even_val.len() as i32;let mut ans: Veci32 Vec::with_capacity(queries.len());for q in queries {let l q[0] as usize;let r q[1] as usize;let k q[2];// 外层二分第 t 个正偶数值为 2*tlet mut lo k;let mut hi k m 2;while lo hi {let mid (lo hi) / 2;let target 2 * mid;// 内层二分统计子数组中值 2*t 的偶数个数let left even_idx.partition_point(|v| v l);let right even_idx.partition_point(|v| v r);let removed if left right {0} else {let slice even_val[left..right];slice.partition_point(|v| v target) as i32};// 前 mid 个偶数中未被移除的个数是否 kif mid - removed k {hi mid;} else {lo mid 1;}}ans.push(2 * lo);}ans}}核心思路二分套二分层次 作用外层二分 对「第 t 个正偶数」二分答案值为 2t。验证条件前 t 个偶数中未被移除的个数 \ge k。内层二分 partition_point 模拟 bisect先锁定子数组区间内的偶数位置再统计其中值 \le 2t 的个数。单调性 随着 t 增大被移除个数只增不减「剩余个数 t - \text{removed}」单调递增保证二分正确。复杂度- 时间O((n q) \cdot \log m \cdot \log(km))其中 m 为偶数总数。- 空间O(n)存储偶数下标和值。验证结果输入 输出nums[1,4,7], queries[[0,2,1],[1,1,2],[0,0,3]] [2, 6, 6]nums[2,5,8], queries[[0,1,2],[1,2,1],[0,2,4]] [6, 2, 12]nums[3,6], queries[[0,1,1],[1,1,3]] [2, 8]nums[1,3,5], queries[[0,2,100]]无偶数 [200]nums[2,4,6,8], queries[[0,3,1]]全偶数 [10]
