Description

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 is4.

In array[1,2,3,4,5], the 1st largest element is5, 2nd largest element is4, 3rd largest element is3and etc.

Challenge

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

Solution

1.Priority Queue 适用于列举前k个element, Complexity O(nlog(n))

2.Partition Sort适用于求第k个element, Complexity O(n)

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
        return kthLargestElementHelper(nums, 0, nums.length - 1, nums.length - k + 1); // kth largest is (nums.length - k + 1)th smallest
    }

    public int kthLargestElementHelper(int[] nums, int left, int right, int k) {
        if (left == k) {
            return nums[left];
        }

        int position = Partition(nums, left, right);
        if (position + 1 == k) {
            return nums[position];
        } else if (position + 1 > k) {
            return kthLargestElementHelper(nums, left, position - 1, k);
        } else {
            return kthLargestElementHelper(nums, position + 1, right, k);
        }
    }

    private int Partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }

            nums[left] = nums[right];

            while (left < right && nums[left] <= pivot) {
                left++;
            }

            nums[right] = nums[left];
        }

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