AcWing 786. 第k个数

活动 - AcWing

 

【快排】按照快排的思想，直到中间分隔点=k

// package AcWing.course;
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {

    // 7:50.  8:06
    static int n, k, ans = 0;
    static int[] arr;
    static StreamTokenizer st;

    static int nextInt() throws Exception {
        st.nextToken();
        return (int)st.nval;
    }

    static void quickSort(int l, int r){
        if(l > r) return;
        int i = l, j = r, pivot = arr[l];
        while(i < j){
            while(i < j && arr[j] > pivot) j--;
            arr[i] = arr[j];
            while(i < j && arr[i] <= pivot) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        if(i == k) {
            ans = arr[i];
            return;
        }else if(i > k){
            quickSort(l, i - 1);
        }else{
            quickSort(i + 1, r);
        }
    }

    public static void main(String[] args) throws Exception {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(System.out);
        n = nextInt();
        k = nextInt() - 1;
        arr = new int[n];
        for(var i = 0; i < n; i++) arr[i] = nextInt();
        quickSort(0, n - 1);
        pw.println(ans);
        pw.flush();
    }

}