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

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]。

解释：

i

queries[i]

nums[li..ri]

移除的偶数

剩余的偶数

ki

ans[i]

0

[0, 2, 1]

[1, 4, 7]

2, 6, 8, …

1

2

1

[1, 1, 2]

2, 6, 8, …

2

6

2

[0, 0, 3]

2, 4, 6, …

3

6

因此，ans = [2, 6, 6]。

题目来自力扣3911。

算法总体思路

本题要求对每个查询，在全局正偶数序列（2, 4, 6, …）中删除指定子数组里出现的偶数后，找出第 k 个剩下的偶数。
由于nums本身严格递增，子数组中的偶数也是严格递增且互不重复，因此我们可以利用“删除偶数在原偶数序列中的序号”来快速定位。

核心思想：
将每个偶数v映射为其在偶数序列中的序号v / 2（从 1 开始）。
对于某个查询，子数组中所有偶数对应的序号构成一个严格递增的集合S（记为被删除的序号）。
我们要求在删除S后，剩下的序号中第k个最小的序号t，然后答案就是2 * t。

预处理

1. 遍历整个nums，找出所有值为偶数的元素，并记录它们的原始下标，存入数组evenPos。

• 因为nums严格递增，所以evenPos中的下标也是严格递增的。

• 这一步耗时 O(n)，n 为nums长度。

每个查询的处理步骤

对于每个查询[l, r, k]，我们按如下过程计算答案：

1. 定位子数组内所有偶数下标

• 在evenPos中，使用二分查找找到第一个≥ l的位置left。

• 再找到第一个≥ r+1的位置right（由于r是闭区间，r+1作为开区间右边界）。

• 则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个被删除偶数之前（若j=0，则在第一个被删除偶数之前；若j=m，则在所有被删除偶数之后）。

• 此时，在所有小于该答案的偶数中，恰好有j个被删除（即pos[0..j-1]），所以该答案在原始偶数序列中的序号为j + k。

• 最终答案为(j + k) * 2。

为什么二分条件正确

• 如果f(j)为真，说明在第j个被删除偶数之前，剩余的偶数个数已经不少于k，那么第k个剩余偶数不可能在第j个被删除偶数之后，答案的序号小于等于nums[pos[j]] / 2（但不会等于它，因为该值已被删除），因此我们可以把搜索范围向左收缩。

• 如果f(j)为假，则说明前面剩余个数不足k，答案必然在第j个被删除偶数之后，搜索范围向右移动。

• 二分查找最终确定分界点，使计算准确。

时间复杂度

• 预处理：遍历一次nums，O(n)，n 为nums长度。

• 每个查询需要三次二分查找：

1. 在evenPos中找left，O(log n)；

2. 找right，O(log n)；

3. 在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]，m=1，二分得到j=0（因为4/2-1-0 = 1 ≥ 1），答案(0+1)*2=2。

• 查询 1：子数组[4]，同样pos=[1]，k=2，f(0)=1-0=1 < 2，f(1)=true（j=m），所以j=1，答案(1+2)*2=6。

• 查询 2：子数组[1]，无偶数，pos=[]，m=0，二分返回j=0，答案(0+3)*2=6。
结果[2,6,6]，与预期一致。

Go完整代码如下：

package main

 import (
    "fmt"
    "sort"
)

 func kthRemainingInteger(nums []int, queries [][]int) []int {
    // 记录所有偶数的下标
    evenPos := []int{}
    for i, x := range nums {
        if x%2 == 0 {
            evenPos = append(evenPos, i)
        }
    }

     ans := make([]int, len(queries))
    for i, q := range queries {
        // 找到询问对应的 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(j int) bool {
            return nums[pos[j]]/2-1-j >= k
        })
        ans[i] = (j + k) * 2
    }
    return ans
}

 func main() {
    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-*-

 import bisect

 def kthRemainingInteger(nums, queries):
    # 收集 nums 中所有偶数元素的下标（因为 nums 严格递增，下标也是递增的）
    even_pos = [i for i, x in enumerate(nums) if x % 2 == 0]
    ans = []
    for l, r, k in queries:
        # 在 even_pos 中定位落在 [l, r] 区间内的下标范围
        left = bisect.bisect_left(even_pos, l)
        right = bisect.bisect_right(even_pos, r)
        pos = even_pos[left:right]   # 这些下标对应的 nums 值都是偶数，且在子数组内
        # 二分查找最小的 j，使得 nums[pos[j]]//2 - 1 - j >= k
        lo, hi = 0, len(pos)
        while lo < hi:
            mid = (lo + hi) // 2
            # 当前偶数在原始偶数序列中的序号（从0开始）减去前面已移除的偶数个数
            if nums[pos[mid]] // 2 - 1 - mid >= k:
                hi = mid
            else:
                lo = mid + 1
        j = lo
        # 第 k 个剩余偶数的原始序号为 j + k，数值为 (j + k) * 2
        ans.append((j + k) * 2)
    return ans

 def main():
    nums = [1, 4, 7]
    queries = [[0, 2, 1], [1, 1, 2], [0, 0, 3]]
    result = kthRemainingInteger(nums, queries)
    print(result)  

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

using namespace std;


 vector kthRemainingInteger(vector& nums, vector 
 
 int 
 >>& queries) { 
 
 
     vector< 
 int 
 > evenPos; 
 
 
      
 // 收集 nums 中所有偶数元素的下标 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < ( 
 int 
 )nums.size(); ++i) { 
 
 
          
 if 
  (nums[i] %  
 2 
  ==  
 0 
 ) { 
 
 
             evenPos.push_back(i); 
 
 
         } 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > ans; 
 
 
     ans.reserve(queries.size()); 
 
 
 
 
      
 for 
  (auto& q : queries) { 
 
 
          
 int 
  l = q[ 
 0 
 ], r = q[ 
 1 
 ], k = q[ 
 2 
 ]; 
 
 
 
 
          
 // 在 evenPos 中定位属于 [l, r] 的下标范围 
 
 
          
 int 
  leftIdx = lower_bound(evenPos.begin(), evenPos.end(), l) - evenPos.begin(); 
 
 
          
 int 
  rightIdx = lower_bound(evenPos.begin(), evenPos.end(), r +  
 1 
 ) - evenPos.begin(); 
 
 
          
 int 
  m = rightIdx - leftIdx;    
 // 该区间内偶数的个数 
 
 
 
 
          
 // 二分查找最小的 j，使得 nums[evenPos[leftIdx + j]] / 2 - 1 - j >= k 
 
 
          
 int 
  lo =  
 0 
 , hi = m; 
 
 
         while (lo < hi) { 
 
 
              
 int 
  mid = (lo + hi) /  
 2 
 ; 
 
 
              
 int 
  idx = evenPos[leftIdx + mid]; 
 
 
              
 if 
  (nums[idx] /  
 2 
  -  
 1 
  - mid >= k) { 
 
 
                 hi = mid; 
 
 
             }  
 else 
  { 
 
 
                 lo = mid +  
 1 
 ; 
 
 
             } 
 
 
         } 
 
 
          
 int 
  j = lo; 
 
 
         ans.push_back((j + k) *  
 2 
 ); 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 1 
 ,  
 4 
 ,  
 7 
 }; 
 
 
     vector 
 
 int 
 >> queries = {{ 
 0 
 ,  
 2 
 ,  
 1 
 }, { 
 1 
 ,  
 1 
 ,  
 2 
 }, { 
 0 
 ,  
 0 
 ,  
 3 
 }}; 
 
 
     vector< 
 int 
 > result = kthRemainingInteger(nums, queries); 
 
 
      
 for 
  ( 
 int 
  x : result) { 
 
 
         cout << x <<  
 " " 
 ; 
 
 
     } 
 
 
     cout << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。