每日一题02
程序员文章站
2022-03-15 21:13:55
...
题目描述:
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
在看到这道题的第一反应就是如下代码,虽然牛客上提交过去了,但是这是投机取巧的方法,主要是忘记了快速排序的思想。
public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here
Arrays.sort(a);
for(int i=1;i<K;i++){
if(a[i]==a[i-1]){
K++;
}
}
return a[a.length-K];
}
}
在复习了快速排序的方法之后,这道题应该是用快排的思想:例如找49个元素里面第24大的元素,那么按如下步骤:1.进行一次快排(将大的元素放在前半段,小的元素放在后半段),假设得到的中轴为p,2.判断p-low+1==k,如果成立,直接输出a[p],(因为前半段有k-1个大于a[p]的元素,故a[p]为第K大的元素)3.如果p-low+1>k,则第K大的元素在前半段,此时更新high=p-1,继续进行步骤1,4.如果p-low+1<k,则第K大的元素在后半段,此时更新low=p+1,且k=k-(p-low+1),继续进行步骤1,由于常规快排要得到整体有序的数组,而此方法每次可以去掉“一半”的元素,故实际的复杂度不是O(nlgn),而是O(n).
public int FindK(int[] a,int n,int K){
return findK(a,0,n-1,K);
}
private int findK(int[] a, int low, int high, int K) {
int part=partition(a,low,high);
if(part-low+1==K){
return a[part];
}
if(K>part-low+1){
return findK(a,part+1,high,K-part+low-1);
}
else{
return findK(a,low,part-1,K);
}
}
private int partition(int[] a, int low, int high) {
int pivot=a[low];
int i=low;
int j=high;
while(i<j){
while(i<j&&a[j]<=pivot){
j--;
}
a[i]=a[j];
while(i<j&&a[i]>=pivot){
i++;
}
a[j]=a[i];
}
a[i]=pivot;
return i;
}