题解 | #寻找第K大#
寻找第K大
http://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
import java.util.*;
public class Solution { public int findKth(int[] a, int n, int K) { sort(a,0,n-1);
// write code here
return a[K-1];
}
public void sort(int[] arr ,int left,int right){
if(left < right){
int mid = partition(arr,left,right);
sort(arr,left,mid);
sort(arr,mid+1,right);
}
}
public int partition(int[] arr ,int left, int right){
int l = left;
int r = right+1;
while(l<r){
while(l<r){
r--;
if(arr[r] > arr[left] )
break;
}
while(l<r){
if(arr[l] < arr[left])
break;
l++;
}
swap(arr,l,r);
}
swap(arr,left,l);
return l;
}
public void swap(int[] arr ,int left, int right){
if(arr[left]==arr[right])
return ;
arr[left] = arr[left]^arr[right];
arr[right] = arr[left]^arr[right];
arr[left] = arr[left]^arr[right];
}
}