共计 2520 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 215. 数组中的第 K 个最大元素 ，难度为 中等。
Tag :「树状数组」、「二分」、「优先队列（堆）」、「疾速抉择」
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请留神，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现工夫复杂度为 $O(n)$ 的算法解决此问题。
示例 1:
输出: [3,2,1,5,6,4], k = 2
输入: 5示例 2:
输出: [3,2,3,1,2,4,5,5,6], k = 4
输入: 4提醒：
- $1 <= k <= nums.length <= 10^5$
- $-10^4 <= nums[i] <= 10^4$
值域映射 + 树状数组 + 二分
除了间接对数组进行排序，取第 $k$ 位的 $O(n\log{n})$ 做法以外。
对于值域大小 小于 数组长度自身时，咱们还能应用「树状数组 + 二分」的 $O(n\log{m})$ 做法，其中 $m$ 为值域大小。
首先值域大小为 $[-10^4, 10^4]$，为了不便，咱们为每个 $nums[i]$ 减少大小为 $1e4 + 10$ 的偏移量，将值域映射到 $[10, 2 \times 10^4 + 10]$ 的空间。
将每个减少偏移量后的 $nums[i]$ 存入树状数组，思考在 $[0, m)$ 范畴内进行二分，假如咱们实在第 $k$ 大的值为 $t$，那么在以 $t$ 为宰割点的数轴上，具备二段性质：
- 在 $[0, t]$ 范畴内的数 $cur$ 满足「树状数组中大于等于 $cur$ 的数不低于 $k$ 个」
- 在 $(t, m)$ 范畴内的数 $cur$ 不满足「树状数组中大于等于 $cur$ 的数不低于 $k$ 个」
二分出后果后再减去刚开始增加的偏移量即是答案。
代码：
class Solution {
int M = 10010, N = 2 * M;
int[] tr = new int[N];
int lowbit(int x) {return x & -x;}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
void add(int x) {for (int i = x; i < N; i += lowbit(i)) tr[i]++;
}
public int findKthLargest(int[] nums, int k) {for (int x : nums) add(x + M);
int l = 0, r = N - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(N - 1) - query(mid - 1) >= k) l = mid;
else r = mid - 1;
}
return r - M;
}
}- 工夫复杂度：将所有数字放入树状数组复杂度为 $O(n\log{m})$；二分出答案复杂度为 $O(\log^2{m})$，其中 $m = 2 \times 10^4$ 为值域大小。整体复杂度为 $O(n\log{m})$
- 空间复杂度：$O(m)$
优先队列（堆）
另外一个容易想到的想法是利用优先队列（堆），因为题目要咱们求的是第 $k$ 大的元素，因而咱们建设一个小根堆。
依据以后队列元素个数或以后元素与栈顶元素的大小关系进行分状况探讨：
- 当优先队列元素有余 $k$ 个，可将以后元素间接放入队列中；
- 当优先队列元素达到 $k$ 个，并且以后元素大于栈顶元素（栈顶元素必然不是答案），可将以后元素放入队列中。
代码：
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
for (int x : nums) {if (q.size() < k || q.peek() < x) q.add(x);
if (q.size() > k) q.poll();}
return q.peek();}
}- 工夫复杂度：$O(n\log{k})$
- 空间复杂度：$O(k)$
疾速抉择
对于给定数组，求解第 $k$ 大元素，且要求线性复杂度，正解为应用「疾速抉择」做法。
基本思路与「疾速排序」统一，每次敲定一个基准值 x，依据以后与 x 的大小关系，将范畴在 $[l, r]$ 的 $nums[i]$ 划分为到两边。
同时利用，利用题目只要求输入第 $k$ 大的值，而不须要对数组进行整体排序，咱们只须要依据划分两边后，第 $k$ 大数会落在哪一边，来决定对哪边进行递归解决即可。
疾速排序模板为面试向重点内容，须要重要把握。
代码：
class Solution {int[] nums;
int qselect(int l, int r, int k) {if (l == r) return nums[k];
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(i, j);
}
if (k <= j) return qselect(l, j, k);
else return qselect(j + 1, r, k);
}
void swap(int i, int j) {int c = nums[i];
nums[i] = nums[j];
nums[j] = c;
}
public int findKthLargest(int[] _nums, int k) {
nums = _nums;
int n = nums.length;
return qselect(0, n - 1, n - k);
}
}- 工夫复杂度：冀望 $O(n)$
- 空间复杂度：疏忽递归带来的额定空间开销，复杂度为 $O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.215 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
