题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第k小数。

数据范围
1≤n≤100000,
1≤k≤n

样例

输入样例：

5 3
2 4 1 5 3

输出样例：

3

算法1快速选择排序

思路(类似二分)

1.快速排序可将数组划分成<=x在左边，>=x在右边的两个区间

2.因此第k个小的数不是在左边，就是在右边

3.第k个小的数下标为k-1，通过和临界坐标比较每次只需递归一边

4.答案总在区间里，最后的最小区间就是答案

时间复杂度

$O(n)$

Java 代码

import java.util.*;

public class Main{
    private static int N = 100010;
    private static int[] a = new int[N];
    public static void main(String[] args){
         Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        for(int i = 0; i < n; i++ ){
            a[i] = scanner.nextInt();
        }
        int l = 0,r = n - 1;
        //传入参数为下标k-1
        System.out.println(quickSort(a,l,r,k-1));
    }
    public static int quickSort(int[] a,int l,int r,int k){
        if(l == r){
            return a[l];
        }
        int x = a[l + r >> 1];
        int i = l - 1,j = r + 1;
        while(i < j){
            do{
                i++;
            }while(a[i] < x);
            do{
                j--;
            }while(a[j] > x);
            if(i < j){
                swap(a,i,j);
            }
        }
        if(k <= j){
            return quickSort(a,l,j,k);
        }else{
            return quickSort(a,j+1,r,k);
        }
    }
     public static void swap(int[] a,int i ,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}