5. Kth Largest Element

Description

Find K-th largest element in an array.

Example

In array [9,3,2,4,8], the 3rd largest element is 4.
In array [1,2,3,4,5], the 1st largest element is 5, 2nd 
largest element is 4, 3rd largest element is 3 and etc.

Solution

//emmm，暂时就采用快排吧，以后有机会再补充
class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        // write your code here
        if(nums.length == 0 || k>nums.length) return 0;
        quick_sort(nums,0,nums.length-1);
        return nums[k-1];
    }

    private void quick_sort(int[] nums,int q,int r){
        if(nums.length == 0) return;
        if(q<r){
            int p = partition(nums,q,r);
            quick_sort(nums,q,p-1);
            quick_sort(nums,p+1,r);
        }
    }

    private int partition(int[] nums,int q,int r){
        int i = q,j = r;
        int x = nums[q];
        while(i<j){
            while(nums[j]<=x&&i<j) j--;
            nums[i] = nums[j];
            while(nums[i]>=x&&i<j) i++;
            nums[j] = nums[i];
        }
        nums[i] = x;
        return i;
    }

};