Kth Largest Element详解编程语言

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. 
 
Note 
You can swap elements in the array 
 
Challenge 
O(n) time, O(1) extra memory.

class Solution { 
    //param k : description of k 
    //param numbers : array of numbers 
    //return: description of return 
    public int kthLargestElement(int k, ArrayList<Integer> numbers) { 
        if (numbers == null || numbers.isEmpty()) return -1; 
 
        int result = qSort(numbers, 0, numbers.size() - 1, k); 
        return result; 
    } 
 
    private int qSort(ArrayList<Integer> nums, int l, int u, int k) { 
        // l should not greater than u 
        if (l >= u) return nums.get(u); 
 
        // index m of nums 
        int m = l; 
        for (int i = l + 1; i <= u; i++) { 
            if (nums.get(i) > nums.get(l)) { 
                m++; 
                Collections.swap(nums, m, i); 
            } 
        } 
        Collections.swap(nums, m, l); 
 
        if (m + 1 == k) { 
            return nums.get(m); 
        } else if (m + 1 > k) { 
            return qSort(nums, l, m - 1, k); 
        } else { 
            return qSort(nums, m + 1, u, k); 
        } 
    } 
}