這道題的核心是二分查找 序號映射把偶數(shù)映射為序號問題轉(zhuǎn)化為從自然數(shù)序列中刪除若干序號后找第 k 個剩余序號再用二分定位答案。題目理解給定嚴(yán)格遞增數(shù)組 nums 和查詢 [l, r, k]從全局正偶數(shù)序列 (2, 4, 6, 8, ...) 中移除 nums[l..r] 子數(shù)組里出現(xiàn)的所有偶數(shù)返回剩下的第 k 個偶數(shù)。核心思路1. 序號映射偶數(shù) v 對應(yīng)序號 v/2從 1 開始全局偶數(shù)序列就是序號序列 1, 2, 3, ...答案 2 × 第k個剩余序號2. 預(yù)處理遍歷 nums把所有偶數(shù)的原始下標(biāo)存入 evenPos因 nums 嚴(yán)格遞增下標(biāo)天然有序3. 每個查詢- 在 evenPos 中二分找到子數(shù)組 [l, r] 內(nèi)的偶數(shù)下標(biāo)區(qū)間 [left, right)- 這些偶數(shù)對應(yīng)的序號構(gòu)成嚴(yán)格遞增的被刪除集合 S- 問題轉(zhuǎn)化為從自然數(shù)序列中刪掉 S找第 k 個剩余序號4. 找第 k 個剩余序號用二分或數(shù)學(xué)方法跳過被刪除的序號定位答案Java 實現(xiàn)class Solution {public int[] kthRemainingInteger(int[] nums, int[][] queries) {int n nums.length;// 預(yù)處理收集所有偶數(shù)元素的原始下標(biāo)ListInteger 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) 就是子數(shù)組 [l,r] 內(nèi)所有偶數(shù)的下標(biāo)// 對應(yīng)的偶數(shù)值為 nums[evenPos[i]]序號為 nums[evenPos[i]] / 2// 從全局偶數(shù)序列中刪掉這些序號后找第 k 個剩余序號long result findKthRemaining(evenPos, nums, left, right, k);ans[q] (int) result;}return ans;}/*** 在被刪除的偶數(shù)序號集合中找第 k 個剩余序號返回對應(yīng)的偶數(shù)值*/private long findKthRemaining(ListInteger evenPos, int[] nums,int left, int right, long k) {// 被刪除的序號個數(shù)int removedCount right - left;if (removedCount 0) {// 沒有偶數(shù)被刪除直接返回第 k 個偶數(shù)return 2L * k;}// 被刪除的序號集合nums[evenPos[i]] / 2i in [left, right)// 這些序號嚴(yán)格遞增// 用二分在值域上找第 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] 中剩余的序號個數(shù)long remaining mid - removedInRange;if (remaining k) {ans mid;hi mid - 1;} else {lo mid 1;}}return 2L * ans;}/*** 計算被刪除序號集合中值 target 的個數(shù)*/private long countRemovedInRange(ListInteger evenPos, int[] nums,int left, int right, long target) {// 在被刪除的偶數(shù)中找值 2*target 的個數(shù)// 即 nums[evenPos[i]] 2*targetlong 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(ListInteger 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(ListInteger 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;}}關(guān)鍵點解析- 序號映射偶數(shù) v → 序號 v/2把偶數(shù)序列刪除問題轉(zhuǎn)化為自然數(shù)序列刪除問題簡化思考- 二分定位子數(shù)組偶數(shù)lowerBound(l) 和 upperBound(r) 快速找到 [l,r] 內(nèi)偶數(shù)的下標(biāo)區(qū)間避免線性掃描- 值域二分找答案在序號值域上二分對每個候選值 mid統(tǒng)計 [1, mid] 中被刪除的序號個數(shù)從而算出剩余序號個數(shù)與 k 比較調(diào)整邊界- 時間復(fù)雜度預(yù)處理 O(n)每個查詢 O(log2M)M 為值域大小整體高效需要我?guī)湍阏硪环荻植檎业耐ㄓ媚０鍐岚?lower_bound、upper_bound 的各種變體方便你直接套用。