题解 | #整数无序数组求第K大数#

import java.util.Comparator;
import java.util.PriorityQueue;
import  java.util.Scanner;

import java.util.*;
public class Main {
    static int result = 0;
    static int n;
    static int[] res;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String temp=in.nextLine();
        String[]res= temp.trim().split(" ");
        int []arr=new int[res.length];
        for(int i=0;i<res.length;i++){
            arr[i]=Integer.parseInt(res[i].trim());
        }

        int k=arr.length-in.nextInt();

        int flag=helper(arr,0,res.length-1);
        while(flag!=k){

            if(flag>k){
                flag=helper(arr,0,flag-1);
            }
            else flag=helper(arr,flag+1,res.length-1);
        }
        System.out.println(arr[k]);

    }

    static int helper(int []arr,int left,int right){
        if(left>=right)return left;
        int left_before=left;
        int pivot=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=pivot)right--;
            while(left<right&&arr[left]<=pivot)left++;
            if(left<right){
                int temp=arr[left];
                arr[left]=arr[right];
                arr[right]=temp;
            }
        }

        arr[left_before]=arr[left];
        arr[left]=pivot;

        return left;

    }
}