题解 | #寻找第K大#快速排序
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
int k = n -K;
int lo = 0, hi = n-1;
while( lo < hi){
int p = quickSort(a,lo,hi);
if( p > k){
hi = p-1;
}else if( p < k){
lo = p+1;
}else{
break;
}
}
return a[k];
}
public int quickSort(int[] arr,int i,int j){
int lo = i,hi =j;
int key = arr[i];
while(lo < hi){
while(lo < hi && key <= arr[hi]){
hi --;
}
while(lo <hi && key >= arr[lo]){
lo ++;
}
exchange( arr, lo, hi);
}
exchange( arr, i, lo);
return lo;
}
public void exchange( int[] arr,int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}