题目描述

模板题：使用快速选择算法选取第k个数。
注意点：
1. 随机初始化分界点
2. 理解模板的 i,j 语义： j表示 下标在j之后的值都大于等于轴点
3. 使用第k个数这个语义对比了话，要注意在 维护初始偏移值

套用模板实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        int res = quickSelect(nums, 0, n - 1, k);
        System.out.println(res);
        return ;
    }
    private static int quickSelect(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return nums[left];
        }
        int pivot = left + (int)(Math.random() * (right + 1 - left));
        pivot = partition(nums, left, right, pivot);
        if (pivot - left + 1 >= k) {
            return quickSelect(nums, left, pivot, k);
        } else {
            return quickSelect(nums, pivot + 1, right, k - (pivot - left + 1));
        }

    }
    private static int partition(int[] nums, int left, int right, int pivot) {
        int i = left - 1, j = right + 1;
        int pivotValue = nums[pivot];
        while (i < j) {
            while (nums[++i] < pivotValue);
            while (nums[--j] > pivotValue);
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        return j;
    }
}

```