Kimi LeetCode 3911. 移除子数组元素后第 K 小偶数 Rust实现
以下是 LeetCode 3911 的 Rust 实现，方法名已按要求使用 `kth_remaining_integer`：
```rust
impl Solution {
pub fn kth_remaining_integer(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
// 预处理：提取所有偶数的下标和值（严格递增）
let mut even_idx: Vec<usize> = Vec::new();
let mut even_val: Vec<i32> = 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: Vec<i32> = 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*t）
let 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 个偶数中，未被移除的个数是否 >= k
if 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(k+m))，其中 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]`