题目描述

)

输入样例

5 3
2 4 1 5 3

输出样例

3

算法1

y总思路，但是自己写的时候在输入流上出现了一点bug

原因如下：
当Scanner读取一个整数后，它实际上也消耗了输入缓冲区中的换行符（如果输入是以换行符结尾的），这可能导致BufferedReader在尝试读取同一行时返回null。

总结：不要同时使用Scanner、BufferedReader读取数据，可能会出现空指针情况。

Java 代码（正解）

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    final static int N = 100010;
    public static int[] arr = new int[N];
    public static int quickSort(int l,int r,int k) {
        if(l >= r)  return arr[l];
        int x = arr[(l+r)/2];

        //两个指针，分别指向数组两端外侧
        int i = l-1;
        int j = r+1;

        while(i < j) {//i < j 防止j = l-1
            do {i++;}while(arr[i] < x);
            do {j--;}while(arr[j] > x);
            if(i < j) {//交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int SL = j-l+1;
        if(k <= SL) {
            return quickSort(l,j,k);
        }
        return quickSort(j+1,r,k-SL);
    }
    public static void main(String[] args) throws Exception{
        InputStreamReader in = new InputStreamReader(System.in);//转换流
        BufferedReader br = new BufferedReader(in);//缓冲读取流

        String[] index = br.readLine().split(" ");
        int num = Integer.parseInt(index[0]);//读取数组长度
        int k = Integer.parseInt(index[1]);

        String[] s = br.readLine().split(" ");//将字符串数据按照空格拆分成字符串数组
        for(int i = 0;i < num;i++) {
            arr[i] = Integer.parseInt(s[i]);//转换成int数组
        }
        br.close();

        int ans = quickSort(0,num-1,k);//快速排序
        System.out.print(ans);
    }
}

算法2

直接对所有数据进行快速排序，输出第k个数arr[k-1]即可