[LintCode] 35 Kth Largest Element 解题报告

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

思路
第K大的数字，其实就是升序排序完成以后index为nums.length - K的数字。我们设这个index为pos，也就是我们要找到的位置。
如果先排序，再找到这个数，时间复杂度是O(nlogn)，不行。
我们用QuickSort的思路对数组进行partition，每次partition完之后，当前cur这个位置之前的数字都比nums[cur]小，而cur之后的数字都比nums[cur]大。
那么我们就看
如果cur比pos小，我们继续partition从cur + 1开始的数，因为前面的数都已经比nums[cur]小了，那么也一定都比nums[pos]小。
如果cur比pos大，我们继续partition从头一直到cur - 1，因为之后的数字都比nums[cur]大，也一定比nums[pos]大。
如果cur正好就是pos，说明我们找到了这个位置，并且这个位置之前的所有数都比他小，之后的数都比他大。

复杂度：
我们用O(n)的时间把T(n)变成T(n/2)。
T(n) = T(n / 2) + O(n) = T(n/4) + O(n) + O(n/2) = ... = O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n)
空间复杂度O(1)。


Code

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 < 0) {
            return -1;
        }
        
        k = nums.length - k;
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k);
        
        return nums[k];
    }
    
    public void partition(int[] nums, int lo, int hi, int k) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int lt = lo;
        int gt = hi;
        int i = lo;
        
        while (i <= gt) {
            if (nums[i] < v) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > v) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        
        if (lt < k) {
            partition(nums, lt + 1, hi, k);
        }
        else if (lt > k) {
            partition(nums, lo, lt - 1, k);
        }
        
        return;
    }
    
    public void exch(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}