共42道题，当前是第38题

Description

（第 $k$ 大的数） 给定一个大小为 $n$ 的数列，寻找数列中第 $k$ 大的值。下方的代码基于快速排序的思想，使用分治策略解决这个问题。 

试补全分治程序。  

1   #include <iostream>
2   using namespace std;
3   
4   int n, k, a[100001];
5   
6   int kth_largest(int l, int r, int k) {
7       int i = l, j = r, t = a[l];
8       while (i < j) {
9           while (i < j && a[j] <= t)
10               ___ (1) ___ ;
11          a[i] = a[j];
12          while (i < j && a[i] >= t)
13               i++;
14          ___ (2) ___
15      }
16      a[i] = t;
17      if ( ___ (3) ___ )
18          return a[i];
19      if ( ___ (4) ___ )
20          return kth_largest(l, i - 1, k);
21      return kth_largest(i+1, r,  ___ (5) ___ );
22  }
23  
24  int main() {
25      cin >> n >> k;
26      for (int i = 1; i <= n; i++)
27          cin >> a[i];
28      cout << kth_largest(1, n, k) << endl;
29      return 0;
30  }

1. C。该空与下一空与快速排序的逻辑相同，易得第 (1) 空填 $j--$，也可以联系上下文对称来选择
2. B。理由同上，当然这里可以发现，第 $11$ 行 $a[i] = a[j]$ 后，$a[j]$ 的值在逻辑上已经空出来了，这里肯定是给 $a[j]$ 赋值
3. D。循环操作结束后能保证区间 $[l,i-1]$ 范围内的数都 $>= a[i]$，区间 $[i+1,r]$ 范围内的数都 $<= a[i]$，所以若 $i-l+1==k$，则说明 $a[i]$ 恰为区间 $[l,r]$ 范围内第 $k$ 大的数。
4. C。若 $i-l+1 > k$，则进区间 $[l,i-1]$ 继续查找第 $k$ 大的数。
5. C。若 $i-l+1 < k$，则区间 $[l,r]$ 范围内第 $k$ 大的是应该在区间 $[i+1,r]$ 范围内，但是因为区间 $[l,i]$ 范围内的 $i-l+1$ 个数都大于等于区间 $[i+1,r]$ 范围内的数，所以应去区间 $[i+1,r]$ 范围内找第 $k-(i-l+1)=k+l-i-1$ 大的数。

Question

___ (1) ___ 处应填（ ）

___ (2) ___ 处应填（ ）

___ (3) ___ 处应填（ ）

___ (4) ___ 处应填（ ）

___ (5) ___ 处应填（ ）

陈伦制作 版权所无 粤ICP备16127491号-1