find Kth largest in an array

题目：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, given [3,2,1,5,6,4] and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

解题思路：
这道题有3种解法：1. 排序；2. 快排思想； 3. heap.。时间复杂度分别为 1. O(nlog(n))；2. Average case time is O(n), worst case time is O(n^2)； 3. Time complexity is O(nlog(k)). Space complexity is O(k) for storing the top k numbers. 这里是标准的快排代码： http://www.algolist.net/Algorithms/Sorting/Quicksort


代码：
快排思想：

public int findKthLargest(int[] nums, int k) {
    if (k < 1 || nums == null) {
        return 0;
    }
    return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}
public int getKth(int k, int[] nums, int start, int end) {
    int pivot = nums[end];
    int left = start;
    int right = end;
    while (true) {
        while (nums[left] < pivot && left < right) {
            left++;
        }
        while (nums[right] >= pivot && right > left) {
            right--;
        }
        if (left == right) {
            break;
        }
        swap(nums, left, right);
    }
    swap(nums, left, end);
    if (k == left + 1) {
        return pivot;
    } else if (k < left + 1) {
        return getKth(k, nums, start, left - 1);
    } else {
        return getKth(k - left - 1, nums, left + 1, end);
    }
}
public void swap(int[] nums, int n1, int n2) {
    int tmp = nums[n1];
    nums[n1] = nums[n2];
    nums[n2] = tmp;
}