【算法】acwing 786 第k个数（模板题）

原题连接

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

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

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

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

数据范围
1≤n≤100000,
1≤k≤n
输入样例：
5 3
2 4 1 5 3
输出样例：
3

这是快排变题，先看一手快排的模板

import java.util.*;

public class Main{
    public static void main (String args[]){
        Scanner sc =  new Scanner(System.in);
        int n = sc.nextInt();
        int [] a = new int [n];
        for(int i = 0; i < n; i++)a[i] = sc.nextInt();

        quickSort(a,0,n-1);

        for(int i = 0; i < n;i++ )System.out.print(a[i] + " ");
    }

    public static void quickSort(int [] a,int l, int r){
        if(l >= r) return;
        int i = l - 1, j = r + 1, x = a [l+r>> 1];
        while(i < j){
            do i ++;while(a[i] < x);
            do j --;while(a[j] > x);

            if( i < j){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        quickSort(a,l,j);
        quickSort(a,j+1,r);
    }
}

这题在递归的时候不需要递归两边处理

• 当左边sl <= k 时 递归左边即可
• 当 sl > k 时，递归右边即可，但此时的k = k - sl

ac code

import java.util.*;

public class Main{
    static int[] a;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        a = new int[n];
        for(int i = 0; i < n; i++)a[i] = sc.nextInt();
        System.out.println(quickSort(0, n - 1, k));
    }

    public static int quickSort(int l,int r,int k){
        if(l == r)return a[l];
        int x = a[l + r >> 1],i = l - 1,j = r + 1;
        while(i < j){
            while(a[++ i] < x);
            while(a[-- j] > x);
            if(i < j){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        int sl = j - l + 1;
        if(k <= sl)return quickSort(l,j,k);

        return quickSort(j + 1,r, k - sl);
    }
}

空间复杂度o(n),
时间复杂度 n + n/2 + n/4 + n / 8 ... ≈2n ，∴o(n)。