AcWing 786. 第k个数（快排应用）

题目链接：https://www.acwing.com/problem/content/description/788/

解法1：

递归性质，设计一个查找函数，不断缩小搜索范围，最终找到第k个数字。符合递归函数设计原则。

解法2：

二分的思想，每次只对第k个数字所在部分进行排序，最终保证，第k个数处在正确的位置。

AC代码：

import java.util.*;

public class Main {
    
    public static int N = (int) 1e5 + 10;
    public static int[] arr = new int[N]; 
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(), k = sc.nextInt();
        
        for (int i = 0; i < n; i ++) arr[i] = sc.nextInt();
        
        int res = quickchoose(arr, 0, n - 1, k);
        
        System.out.println(res);
    }
    
    // 解法1
    public static int quickchoose(int[] arr, int l, int r, int k) {
        if (l >= r) return arr[l];
        
        int pivot = arr[l + r >> 1];
        
        int i = l - 1, j = r + 1;
        
        while (i < j) {
            do i ++; while(arr[i] < pivot);
            do j --; while(arr[j] > pivot);
            
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        
        if (k <= (j - l + 1)) return quickchoose(arr, l, j, k);
        else return quickchoose(arr, j + 1, r, k - (j - l + 1));
    }
    
    // 解法2
    public static int quickchoose2(int[] arr, int l, int r, int k) {
        if (l >= r) return arr[k - 1];
        
        int pivot = arr[l + r >> 1];
        
        int i = l - 1, j = r + 1;
        
        while (i < j) {
            do i ++; while(arr[i] < pivot);
            do j --; while(arr[j] > pivot);
            
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        
        
        if (k <= j + 1) return quickchoose2(arr, l, j, k);
        else return quickchoose2(arr, j + 1, r, k);
    }
}