Kth Largest Element
最后更新于：2022-04-02 01:08:44
# 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 numbers) {
if (numbers == null || numbers.isEmpty()) return -1;
int result = qSort(numbers, 0, numbers.size() - 1, k);
return result;
}
private int qSort(ArrayList 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).
';