[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;
    }
    
}