题目描述

blablabla

样例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();

        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }

        System.out.print("" + quickSort(nums, 0, n - 1, k));
    }

    private static int quickSort(int[] q, int l , int r, int k) {
        // 递归终止条件
        if (l == r) return q[l];

        // 取分界点
        int x = q[l];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            while (q[++i] < x);
            while (q[--j] > x);
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        // 左半边查找
        if (k <= j - l + 1) return quickSort(q, l, j, k);
        // 右半边查找第k - 前半段长度
        return quickSort(q, j + 1, r, k - (j - l + 1));
    }
}