题解 | #寻找第K大#
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int k) {
// write code here
return findKth(a, 0, n - 1, n - k + 1);
}
public int findKth(int[] a, int start, int end, int k){
if(start >= end) return a[start];
int left = start - 1, right = end + 1, mid = a[left + (right - left)/2];
while(left < right){
do left++; while(mid > a[left]);
do right--; while(mid < a[right]);
if(left < right){swap(a, left, right);}
else break;
}
if(right >= k-1){ return findKth(a,start,right,k);}//因为第k大对应下标为k-1}
else {return findKth(a, right + 1, end, k);}
}
public static void swap(int[] q, int p1, int p2){
int temp = q[p1];
q[p1] = q[p2];
q[p2] = temp;
}
} 
