# Kth Largest Element ### Source - leetcode: [Kth Largest Element in an Array | LeetCode OJ](https://leetcode.com/problems/kth-largest-element-in-an-array/) - lintcode: [(5) Kth Largest Element](http://www.lintcode.com/en/problem/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. ~~~ ### 題解 找第 K 大數，基于比較的排序的方法時間復雜度為 O(n)O(n)O(n), 數組元素無區間限定，故無法使用線性排序。由于只是需要找第 K 大數，這種類型的題通常需要使用快排的思想解決。[Quick Sort](http://algorithm.yuanbin.me/zh-cn/basics_sorting/quick_sort.html) 總結了一些經典模板。這里比較基準值最后的位置的索引值和 K 的大小關系即可遞歸求解。 ### Java ~~~ 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); } } } ~~~ ### 源碼分析 遞歸的終止條件有兩個，一個是左邊界的值等于右邊界(實際中其實不會有 l > u), 另一個則是索引值 `m + 1 == k`.這里找的是第 K 大數，故為降序排列，for 循環中使用`nums.get(i) > nums.get(l)` 而不是小于號。 ### 復雜度分析 最壞情況下需要遍歷 n+n?1+...+1=O(n2) n + n - 1 + ... + 1 = O(n^2)n+n?1+...+1=O(n2), 平均情況下 n+n/2+n/4+...+1=O(2n)=O(n)n + n/2 + n/4 + ... + 1 = O(2n)=O(n)n+n/2+n/4+...+1=O(2n)=O(n). 故平均情況時間復雜度為 O(n)O(n)O(n). 交換數組的值時使用了額外空間，空間復雜度 O(1)O(1)O(1).