Kimi LeetCode 3911. 移除子数组元素后第 K 小偶数 Python3实现

以下是可直接在 LeetCode 提交的 Python3 完整实现方法名已按题目要求使用 kthRemainingIntegerpythonimport bisectclass Solution:def kthRemainingInteger(self, nums: list[int], queries: list[list[int]]) - list[int]:对每个查询 [l, r, k]- 从无限正偶数序列 2,4,6,8,... 中移除子数组 nums[l..r] 里的偶数- 返回剩余序列中第 k 小的偶数核心思路二分套二分- 外层二分假设答案是第 t 个正偶数值为 2*t- 内层二分统计子数组中值 2*t 的偶数个数- 验证t - removed_count k 是否成立# 预处理提取所有偶数的下标和值nums 严格递增故 even_val 也严格递增even_idx [] # 偶数在原数组中的下标even_val [] # 偶数的值for i, x in enumerate(nums):if x % 2 0:even_idx.append(i)even_val.append(x)m len(even_val) # 全局偶数个数def count_removed(l: int, r: int, t: int) - int:统计子数组 nums[l..r] 中值 2*t 的偶数个数# 步骤1找到下标落在 [l, r] 范围内的偶数位置left bisect.bisect_left(even_idx, l)right bisect.bisect_right(even_idx, r)if left right:return 0# 步骤2在这些偶数中值 2*t 的个数even_val 严格递增可直接二分return bisect.bisect_right(even_val, 2 * t, left, right) - leftans []for l, r, k in queries:# 二分查找第 t 个正偶数# 下界k至少第 k 个偶数# 上界k 全局偶数个数 余量安全上界lo, hi k, k m 2while lo hi:mid (lo hi) // 2removed count_removed(l, r, mid) # 子数组中被移除的偶数个数remaining mid - removed # 前 mid 个偶数中剩余的个数if remaining k:hi mid # 答案可能更小收缩右边界else:lo mid 1 # 剩余不够需要更大的 tans.append(2 * lo) # 第 t 个正偶数的值是 2*treturn ans核心思路二分套二分层次 作用外层二分 对「第 t 个正偶数」二分。若前 t 个偶数即 2,4,\dots,2t中未被移除的个数 \ge k则答案 \le 2t。内层二分 count_removed 先用 bisect_left/right 锁定子数组区间内的偶数位置再用 bisect_right 统计其中值 \le 2t 的个数。单调性 随着 t 增大被移除的个数只增不减因此「剩余个数 t - \text{removed}」单调递增保证二分正确。复杂度- 时间O((n q) \cdot \log m \cdot \log(km))其中 n \text{len(nums)}q \text{len(queries)}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]