java 快速选择 MLE 求助

P1923 【深基9.例4】求第 k 小的数

Warren1321 @ 2024-07-22 12:54:23


import java.io.*;
import java.util.StringTokenizer;

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

public class Main {
    public static void main(String[] args) {
        FastReader reader = new FastReader();
        int n = reader.nextInt();
        int k = reader.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = reader.nextInt();
        }

        int kthSmallest = quickSelect(arr, 0, n-1, k);

        System.out.println(kthSmallest);
    }

    private static void swap (int[]array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static int partition (int[] array, int left, int right){
        int pivot = array[right];
        int i = left;

        for (int j = left; j < right; j++) {
            if (array[j] < pivot){
                swap(array, i, j);
                i++;
            }

        }
        swap(array, i, right);
        return i;
    }

    private static int quickSelect(int[] array, int left, int right, int k){

        if (left == right){
            return array[left];
        }

        int pivotIndex = partition(array, left, right);

        if (k == pivotIndex){
            return array[k];
        }
        else if (k < pivotIndex) {
            return quickSelect(array, left, pivotIndex - 1, k);

        }
        else {
            return quickSelect(array, pivotIndex + 1, right, k);
        }
    }
}

最后两个点MLE,求助大佬


|