寻找第K个大(方法一:快速排序)
寻找第K大
http://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf
我用的是java实现快速排序,先排序好 ,然后倒着找就行了,也通过! 适合初学者学,还可以建大顶堆,建立后,每次调整根元素,然后在输出第K个即可,想要建堆算法实现的可以评论,我写出来
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
if(a.length==n){
quickSort(a,0,n-1);
int p = a.length-1;
int i = 1;
while(i<K){
p--;
i++;
}
return a[p];
}
return 0;
}
public void quickSort(int [] a,int low,int high){
if(low<high){
int temp = a[low];//1
int i = low;//0
int j = high;//4
while(i<j){
while(temp<a[j]&&i<j) j--;
a[i]=a[j];
while(temp>=a[i]&&i<j) i++;
a[j]=a[i];
}
a[i]=temp;
quickSort(a,low,i-1);
quickSort(a,i+1,high);
}else{
return;
}
}
}