Kth Largest Element 5

Question

Find K-th largest element in an array.

Notice

You can swap elements in the 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.

Challenge

O(n) time, O(1) extra memory.

Solution

用quick sort来解，平均时间复杂度为O(n)。

1. 初始为求数组中从头到尾第nums.length - k + 1个元素（即从后往前第k个元素，即第k最大元素，）

2. 然后用quick sort并返回分割点的index

3. 如果该分割点正好是第nums.length - k + 1个元素，则找到并返回；否则若该分割点比k小，则递归地在数组index＋1－数组尾区间寻找，若该分割点比k大，则递归地在数组头－index－1区间寻找

代码如下：

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 == null || nums.length == 0 || k < 1 || k > nums.length){
            return -1;
        }

        //第k大就是从小到大排第nums.length - k + 1大
        return kthLargestHelper(nums, 0, nums.length - 1, nums.length - k + 1);
    }
    //quick sort模板
    private int kthLargestHelper(int[] nums, int l, int r, int k){
        if(l == r){
            return nums[l];
        }

        int position = partition(nums, l, r);
        if(position + 1 == k){
            return nums[position];
        }else if(position + 1 > k){
            return kthLargestHelper(nums, l, position - 1, k);
        }else{
            return kthLargestHelper(nums, position + 1, r, k);
        }
    }

    private int partition(int[] nums, int l, int r){
        int start = l;
        int end = r;
        int pivot = nums[end];

        while(start < end){
            while(start < end && nums[start] <= pivot){
                start++;
            }
            nums[end] = nums[start];
            while(start < end && nums[end] > pivot){
                end--;
            }
            nums[start] = nums[end];
        }

        nums[start] = pivot;
        return start;
    }
};