[215]Kth Largest Element in an Array
2956 ワード
public class Solution {
public int findKthLargest(int[] nums, int k) {
return find(nums,nums.length-k,0,nums.length-1);
}
public int find(int[]nums,int k,int start,int end){
if(start>=end) return nums[start];
int m=partition(nums,start,end);
if(m==k) return nums[m];
if(m<k){
return find(nums,k,m+1,end);
}else{
return find(nums,k,start,m-1);
}
}
public int partition(int nums[],int start,int end){
int temp=nums[start];
while(start<end){
while(start<end&&nums[end]>=temp)end--;
nums[start]=nums[end];
while(start<end&&nums[start]<=temp)start++;
nums[end]=nums[start];
}
nums[start]=temp;
return start;
}
}