题目描述

blablabla

快排应用(根据特性只递归一边)

(时间复杂度) $O(n)$

import java.io.*;
import java.util.*;

public class Main{
    private static int N = 100010;
    private static int n,k;
    private static int[] q = new int[N];

    private static int quickFind(int[] q,int l,int r,int k){
        /**
         * 快速选择算法(基于快排)
         * 1.在partition的过程中记录左边区间长度Left
         * 2.如果k<=left,则只需要递归左边即可
         *   如果k > left,则只需要递归右边即可切目标数是右边的第k-Left个数
         * 每次递归的时候都保证答案在区间内部，当最后l==r时这个数就是答案
         **/ 
         if(l == r) return q[l];
         int x = q[l],i = l-1,j = r+1;
         while(i < j){
             do{
                 i++;
             }while(q[i] < x);
             do{
                 j--;
             }while(q[j] > x);
             if(i < j){
                 int tmp = q[i];
                 q[i] = q[j];
                 q[j] = tmp;
             }
         }
         int Left = j - l + 1;
         if(k <= Left) return quickFind(q,l,j,k);
         else return quickFind(q,j+1,r,k-Left);
    }
    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split("\\s+");
        n = Integer.valueOf(s[0]);
        k = Integer.valueOf(s[1]);
        s = in.readLine().split("\\s+");
        for(int i = 0 ; i < n ; i++){
            q[i] = Integer.valueOf(s[i]);
        }
        int ans = quickFind(q,0,n-1,k);
        System.out.println(ans);
    }
}