给定一个整数数组，找出数组中第K大的数
输入、输出描述
输入：
arr: 整数数组 n: 数组长度 k: 取值1到len(arr)的整数
输出：
第k大的数
Example
输入：
arr=[1,3,6,2,4] n=5 k=2
输出：
4
代码：
import java.util.*;
public class Main {
public int solution(int[] arr,int n,int k) {
if (n ==1)
return arr[0];
int index = n - k ;
return qsort(arr, 0, n-1, index);
}
public int qsort(int[] a,int l,int r,int index) {
int i = partion(a, l, r);
if(i==index)
return a[index];
else if (index < i)
return qsort(a, l, i-1,index);
else
return qsort(a, i+1, r,index);
}
public int partion(int a[],int left,int right) {
Random random= new Random();
//System.out.println(right+"-"+left);
int randIndex = random.nextInt(right-left+1)+left;
//System.out.println(randIndex);
swap(a, randIndex, right);
int pivot = a[right];
int index =left;
for(int i=left;i<right;i++){
if(a[i]<pivot)
swap(a, index++, i);
}
swap(a, index, right);
return index;
}
public void swap(int[] a,int i,int j) {
int t =a[i];
a[i] = a[j];
a[j] =t;
}
}
评论专区
