第k个数（题解）

给定一个长度为n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第k个数。
输入格式
第一行包含两个整数n和k。
第二行包含n个整数(所有整数均在1～10^9范围内)，表示整数数列。
输出格式
输出一个整数，表示数列的第k小数。
数据范围
1<n≤100000,1<k≤n

输入样例：

  

   

    

     

    
    

     

      5 3
     
    
   

    

     

    
    

     

      2 4 1 5 3
     
    
  
 

输出样例：

3

 

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int N = 100010;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int q[N];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int quick_sort(int q[], int l, int r, int k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if (l >= r) return q[l];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
     
    
   

    

     

    
    

     
    while (i < j)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        do i ++ ; while (q[i] < x);
     
    
   

    

     

    
    

     
        do j -- ; while (q[j] > x);
     
    
   

    

     

    
    

     
        if (i < j) swap(q[i], q[j]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    if (j - l + 1 >= k) return quick_sort(q, l, j, k);
     
    
   

    

     

    
    

     
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n, k;
     
    
   

    

     

    
    

     

          scanf("%d%d", &n, &k);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          cout << quick_sort(q, 0, n - 1, k) << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

 说实话，我觉得这个题目意义不大了，不就是要第k个吗？我一手直接sort然后输出第k个。

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120592890