2026-08-07：移除子数组元素后第 K 小偶数。用go语言，给定一个严格递增的整数数组 nums，以及一组查询，每个查询包含三个整数 l、r 和 k。 对于每个查询，我们只看 nums 中下标从

2026-08-07移除子数组元素后第 K 小偶数。用go语言给定一个严格递增的整数数组 nums以及一组查询每个查询包含三个整数 l、r 和 k。对于每个查询我们只看 nums 中下标从 l 到 r 的这一段连续子数组。接着考虑所有正偶数组成的无限序列2, 4, 6, 8, 10, …从这个序列中剔除掉那些正好等于上述子数组里出现的数值的元素。剔除之后序列仍然保持从小到大排列我们需要找出这个新序列中的第 k 个最小的整数。最后将每个查询对应的第 k 个最小整数按顺序放入结果数组中返回。注意nums 本身是严格递增的所以任意子数组中的元素也是严格递增且互不相同的。1 nums.length 100000。1 nums[i] 1000000000。nums 是严格递增的。1 queries.length 100000。queries[i] [li, ri, ki]。0 li ri nums.length。1 ki 1000000000。输入 nums [1,4,7], queries [[0,2,1],[1,1,2],[0,0,3]]。输出 [2,6,6]。解释iqueries[i]nums[li…ri]移除的偶数剩余的偶数kians[i]0[0, 2, 1][1, 4, 7][4]2, 6, 8, …121[1, 1, 2][4][4]2, 6, 8, …262[0, 0, 3][1][]2, 4, 6, …36因此ans [2, 6, 6]。题目来自力扣3911。算法总体思路本题要求对每个查询在全局正偶数序列2, 4, 6, …中删除指定子数组里出现的偶数后找出第 k 个剩下的偶数。由于nums本身严格递增子数组中的偶数也是严格递增且互不重复因此我们可以利用“删除偶数在原偶数序列中的序号”来快速定位。核心思想将每个偶数v映射为其在偶数序列中的序号v / 2从 1 开始。对于某个查询子数组中所有偶数对应的序号构成一个严格递增的集合S记为被删除的序号。我们要求在删除S后剩下的序号中第k个最小的序号t然后答案就是2 * t。预处理遍历整个nums找出所有值为偶数的元素并记录它们的原始下标存入数组evenPos。因为nums严格递增所以evenPos中的下标也是严格递增的。这一步耗时 O(n)n 为nums长度。每个查询的处理步骤对于每个查询[l, r, k]我们按如下过程计算答案1. 定位子数组内所有偶数下标在evenPos中使用二分查找找到第一个≥ l的位置left。再找到第一个≥ r1的位置right由于r是闭区间r1作为开区间右边界。则evenPos[left : right]就是所有落在[l, r]区间内的偶数下标记为数组pos其长度为m。若m 0说明子数组中没有偶数删除集合为空那么第k个剩余偶数就是整个偶数序列的第k个即2 * k。2. 将子数组偶数映射为序号并理解删除影响对于pos中的第j个元素0 ≤ j m其对应的偶数值为nums[pos[j]]该偶数在全局偶数序列中的序号为nums[pos[j]] / 2。在考虑这个偶数之前全局序号小于它的偶数共有nums[pos[j]] / 2 - 1个。由于pos[0..j-1]都是比它更小的被删除偶数共j个所以在所有小于该偶数的偶数中被删除的个数正好是j。因此在该偶数之前不包括它本身剩余的偶数个数为剩余个数 (nums[pos[j]] / 2 - 1) - j。3. 二分查找第k个剩余偶数落在哪个区间我们需要在所有被删除偶数共m个中找到“分界点”。定义函数f(j)其中0 ≤ j ≤ m当j m时表示所有被删除偶数都已考虑完毕此时可以认为f(m) true即第k个剩余偶数一定在所有被删除偶数之后。当0 ≤ j m时f(j) ( (nums[pos[j]] / 2 - 1 - j) ≥ k )。由于nums严格递增且偶数至少增加 2可证明f(j)的值随着j增大从false单调变为true。因此可以在[0, m]上进行二分查找找到最小的j使得f(j)成立。4. 根据分界点计算答案找到的j表示在前j个被删除偶数之前已经有至少k个剩余偶数但在前j-1个之前不够。因此第k个剩余偶数一定位于第j-1个被删除偶数之后、第j个被删除偶数之前若j0则在第一个被删除偶数之前若jm则在所有被删除偶数之后。此时在所有小于该答案的偶数中恰好有j个被删除即pos[0..j-1]所以该答案在原始偶数序列中的序号为j k。最终答案为(j k) * 2。为什么二分条件正确如果f(j)为真说明在第j个被删除偶数之前剩余的偶数个数已经不少于k那么第k个剩余偶数不可能在第j个被删除偶数之后答案的序号小于等于nums[pos[j]] / 2但不会等于它因为该值已被删除因此我们可以把搜索范围向左收缩。如果f(j)为假则说明前面剩余个数不足k答案必然在第j个被删除偶数之后搜索范围向右移动。二分查找最终确定分界点使计算准确。时间复杂度预处理遍历一次numsO(n)n 为nums长度。每个查询需要三次二分查找在evenPos中找leftO(log n)找rightO(log n)在pos上二分O(log m) ≤ O(log n)。总查询数为 q所以总时间复杂度为O(n q log n)。额外空间复杂度存储evenPos数组最多 O(n)。存储答案数组O(q)。其他临时变量 O(1)。因此总额外空间复杂度为O(n q)。最终回答示例对于题中示例nums [1,4,7]queries [[0,2,1],[1,1,2],[0,0,3]]过程可归纳为预处理的evenPos [1]只有下标 1 的 4 是偶数。查询 0子数组[1,4,7]pos [1]m1二分得到j0因为4/2-1-0 1 ≥ 1答案(01)*22。查询 1子数组[4]同样pos[1]k2f(0)1-01 2f(1)truejm所以j1答案(12)*26。查询 2子数组[1]无偶数pos[]m0二分返回j0答案(03)*26。结果[2,6,6]与预期一致。Go完整代码如下packagemainimport(fmtsort)funckthRemainingInteger(nums[]int,queries[][]int)[]int{// 记录所有偶数的下标evenPos:[]int{}fori,x:rangenums{ifx%20{evenPosappend(evenPos,i)}}ans:make([]int,len(queries))fori,q:rangequeries{// 找到询问对应的 evenPos 的子数组l:sort.SearchInts(evenPos,q[0])r:sort.SearchInts(evenPos,q[1]1)pos:evenPos[l:r]k:q[2]// 推导过程见 1539 题解j:sort.Search(len(pos),func(jint)bool{returnnums[pos[j]]/2-1-jk})ans[i](jk)*2}returnans}funcmain(){nums:[]int{1,4,7}queries:[][]int{{0,2,1},{1,1,2},{0,0,3}}result:kthRemainingInteger(nums,queries)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importbisectdefkthRemainingInteger(nums,queries):# 收集 nums 中所有偶数元素的下标因为 nums 严格递增下标也是递增的even_pos[ifori,xinenumerate(nums)ifx%20]ans[]forl,r,kinqueries:# 在 even_pos 中定位落在 [l, r] 区间内的下标范围leftbisect.bisect_left(even_pos,l)rightbisect.bisect_right(even_pos,r)poseven_pos[left:right]# 这些下标对应的 nums 值都是偶数且在子数组内# 二分查找最小的 j使得 nums[pos[j]]//2 - 1 - j klo,hi0,len(pos)whilelohi:mid(lohi)//2# 当前偶数在原始偶数序列中的序号从0开始减去前面已移除的偶数个数ifnums[pos[mid]]//2-1-midk:himidelse:lomid1jlo# 第 k 个剩余偶数的原始序号为 j k数值为 (j k) * 2ans.append((jk)*2)returnansdefmain():nums[1,4,7]queries[[0,2,1],[1,1,2],[0,0,3]]resultkthRemainingInteger(nums,queries)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;vectorintkthRemainingInteger(vectorintnums,vectorvectorintqueries){vectorintevenPos;// 收集 nums 中所有偶数元素的下标for(inti0;i(int)nums.size();i){if(nums[i]%20){evenPos.push_back(i);}}vectorintans;ans.reserve(queries.size());for(autoq:queries){intlq[0],rq[1],kq[2];// 在 evenPos 中定位属于 [l, r] 的下标范围intleftIdxlower_bound(evenPos.begin(),evenPos.end(),l)-evenPos.begin();intrightIdxlower_bound(evenPos.begin(),evenPos.end(),r1)-evenPos.begin();intmrightIdx-leftIdx;// 该区间内偶数的个数// 二分查找最小的 j使得 nums[evenPos[leftIdx j]] / 2 - 1 - j kintlo0,him;while(lohi){intmid(lohi)/2;intidxevenPos[leftIdxmid];if(nums[idx]/2-1-midk){himid;}else{lomid1;}}intjlo;ans.push_back((jk)*2);}returnans;}intmain(){vectorintnums{1,4,7};vectorvectorintqueries{{0,2,1},{1,1,2},{0,0,3}};vectorintresultkthRemainingInteger(nums,queries);for(intx:result){coutx ;}coutendl;return0;}