题解 | #整数无序数组求第K大数#
整数无序数组求第K大数
http://www.nowcoder.com/practice/097ab63cffa847d89716f2ca8c23524f
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;
}
}
