题目描述
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 O(nlogn),空间复杂度 O(1)
示例
- 示例1
输入:[1,3,5,2,2],5,3
输出:2 - 示例2
输入:[10,10,9,9,8,7,5,6,4,3,4,2],12,3
输出:9
说明:去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9 。
方法思路
典型的快速排序
1、进行一次快排,大元素在左,小元素在右,得到的中轴p点;
2、如果 p - low + 1 = k ,那么p点就是第K大。
3、如果 p - low + 1 > k,则第k大的元素在左半段,更新high = p - 1,执行step 1。
4、如果 p - low + 1 < k,则第k大的元素在右半段,更新low = p + 1, 且 k = k - (p - low + 1),排除掉前面部分更大的元素,再执行step 1。
import java.util.*;
public class Solution {
//常规的快排划分,但是这次是大数在左
public int partion(int[] a,int low,int high){
int temp = a[low];
while(low<high){
//小于标杆的在右
while(low<high && a[high]<=temp){
high--;
}
if(low==high){
break;
}else{
a[low] = a[high];
}
//大于标杆的在左
while(low<high && a[low]>=temp){
low++;
}
if(low==high){
break;
}else{
a[high] = a[low];
}
}
a[low] = temp;
return low;
}
public int quickSort(int[] a,int low,int high,int K){
//先进行一轮划分,p下标左边的都比它大,下标右边都比它小
int p = partion(a,low,high);
//若p刚好是第K个点,则找到
if(K == p-low+1){
return a[p];
}else if(p-low+1>K){
//从头到p超过k个数组,则目标在左边
return quickSort(a,low,p-1,K);
}else{
//否则,在右边,递归右边,但是需要减去左边最大的数字的数量
return quickSort(a,p+1,high,K-(p-low+1));
}
}
public int findKth(int[] a, int n, int K) {
// write code here
return quickSort(a,0,n-1,K);
}
}
网友评论