千问 LeetCode 3911. 移除子数组元素后第 K 小偶数 Java实现

这道题的核心是二分查找 + 序号映射：把偶数映射为序号，问题转化为"从自然数序列中删除若干序号后找第 k 个剩余序号"，再用二分定位答案。

题目理解

给定严格递增数组 nums 和查询 [l, r, k]：从全局正偶数序列 (2, 4, 6, 8, ...) 中，移除 nums[l..r] 子数组里出现的所有偶数，返回剩下的第 k 个偶数。

核心思路

1. 序号映射：偶数 v 对应序号 v/2（从 1 开始），全局偶数序列就是序号序列 1, 2, 3, ...，答案 = 2 × 第k个剩余序号
2. 预处理：遍历 nums，把所有偶数的原始下标存入 evenPos（因 nums 严格递增，下标天然有序）
3. 每个查询：
- 在 evenPos 中二分找到子数组 [l, r] 内的偶数下标区间 [left, right)
- 这些偶数对应的序号构成严格递增的"被删除集合" S
- 问题转化为：从自然数序列中删掉 S，找第 k 个剩余序号
4. 找第 k 个剩余序号：用二分或数学方法，跳过被删除的序号定位答案

Java 实现

class Solution {
public int[] kthRemainingInteger(int[] nums, int[][] queries) {
int n = nums.length;

// 预处理：收集所有偶数元素的原始下标
List<Integer> evenPos = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (nums[i] % 2 == 0) {
evenPos.add(i);
}
}

int[] ans = new int[queries.length];

for (int q = 0; q < queries.length; q++) {
int l = queries[q][0], r = queries[q][1], k = queries[q][2];

// 二分找到 evenPos 中第一个 >= l 的位置
int left = lowerBound(evenPos, l);
// 二分找到 evenPos 中第一个 > r 的位置
int right = upperBound(evenPos, r);

// evenPos[left..right) 就是子数组 [l,r] 内所有偶数的下标
// 对应的偶数值为 nums[evenPos[i]]，序号为 nums[evenPos[i]] / 2
// 从全局偶数序列中删掉这些序号后，找第 k 个剩余序号

long result = findKthRemaining(evenPos, nums, left, right, k);
ans[q] = (int) result;
}

return ans;
}

/**
* 在被删除的偶数序号集合中，找第 k 个剩余序号，返回对应的偶数值
*/
private long findKthRemaining(List<Integer> evenPos, int[] nums,
int left, int right, long k) {
// 被删除的序号个数
int removedCount = right - left;

if (removedCount == 0) {
// 没有偶数被删除，直接返回第 k 个偶数
return 2L * k;
}

// 被删除的序号集合：nums[evenPos[i]] / 2，i in [left, right)
// 这些序号严格递增
// 用二分：在值域上找第 k 个不在被删除集合中的序号

long lo = 1, hi = 2L * (k + removedCount); // 上界足够大
long ans = hi;

while (lo <= hi) {
long mid = lo + (hi - lo) / 2;
// 计算 [1, mid] 中有多少个被删除的序号
long removedInRange = countRemovedInRange(evenPos, nums, left, right, mid);
// [1, mid] 中剩余的序号个数
long remaining = mid - removedInRange;

if (remaining >= k) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}

return 2L * ans;
}

/**
* 计算被删除序号集合中，值 <= target 的个数
*/
private long countRemovedInRange(List<Integer> evenPos, int[] nums,
int left, int right, long target) {
// 在被删除的偶数中，找值 <= 2*target 的个数
// 即 nums[evenPos[i]] <= 2*target
long val = 2L * target;
int lo = left, hi = right - 1;
int pos = left - 1;

while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[evenPos.get(mid)] <= val) {
pos = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}

return pos - left + 1;
}

private int lowerBound(List<Integer> list, int target) {
int lo = 0, hi = list.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (list.get(mid) >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}

private int upperBound(List<Integer> list, int target) {
int lo = 0, hi = list.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (list.get(mid) > target) hi = mid;
else lo = mid + 1;
}
return lo;
}
}

关键点解析

- 序号映射：偶数 v → 序号 v/2，把"偶数序列删除"问题转化为"自然数序列删除"问题，简化思考
- 二分定位子数组偶数：lowerBound(l) 和 upperBound(r) 快速找到 [l,r] 内偶数的下标区间，避免线性扫描
- 值域二分找答案：在序号值域上二分，对每个候选值 mid，统计 [1, mid] 中被删除的序号个数，从而算出剩余序号个数，与 k 比较调整边界
- 时间复杂度：预处理 O(n)，每个查询 O(log²M)（M 为值域大小），整体高效

需要我帮你整理一份"二分查找"的通用模板吗？包括 lower_bound、upper_bound 的各种变体，方便你直接套用。