有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
说这一行代码数组越界int mid = partition(a,left,right);
case通过率为0.00%
Exception in thread "main" java.lang.StackOverflowError
at Finder.quickSort(Finder.java:31)
import java.util.*;
public class Finder {
//交换方法
public void swap(int []a,int l,int r){
int temp;
temp = a[r];
a[r] = a[l];
a[l] = temp;
}
//一次快排
public int partition (int []a, int left ,int right){
while(left<right){
while(left<right&&a[right]>a[left]){
right--;
}
if(left<right)
swap(a,left,right);
while(left<right&&a[left]<a[right]){
left++;
}
if(left<right)
swap(a,left,right);
}
return left;
}
//快排算法
public void quickSort(int[]a ,int left, int right ){
int mid = partition(a,left,right);
quickSort(a,left,mid-1);
quickSort(a,mid+1,right);
}
public int findKth(int[] a, int n, int K) {
// write code here
quickSort(a,0,n-1);
return a[K-1];
}
}