1、第k个数&快速选择

AcWing 786. 第k个数

import java.util.*;

//ACWing
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int goal = sc.nextInt();
        int[] shuzu = new int[len];
        for (int i = 0; i < len; i++) {
            shuzu[i] = sc.nextInt();
        }
        int sum = quickSelect(shuzu, goal, 0, len - 1);
//        maopaoSort(shuzu, len);
//        selectSort(shuzu, len);

        System.out.println(sum);
    }

    //快速选择
    static int quickSelect(int[] s, int goal, int l, int r) {
        if (l >= r)
            return s[goal-1];
        int res = 0;
        int flag = s[l];
        int p_i = l, p_j = r;
        while (p_i < p_j) {
            while (p_i < p_j && s[p_j] >= flag) p_j--;
            while (p_i < p_j && s[p_i] <= flag) p_i++;
            int temp = s[p_i];
            s[p_i] = s[p_j];
            s[p_j] = temp;
            if (p_i >= p_j) {
                int temp0 = s[l];
                s[l] = s[p_i];
                s[p_i] = temp0;
            }
        }
        if ((goal-1) != p_i) {
            if ((goal-1) < p_i)
                res = quickSelect(s, goal, l, p_i - 1);
            if ((goal-1) > p_i)
                res = quickSelect(s, goal, p_i + 1, r);
            return res;
        } else
            return s[goal-1];
    }
}