这是 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
提示:
代码:
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;
}
}
优先队列(堆)
另外一个容易想到的想法是利用优先队列(堆),由于题目要我们求的是第 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();
}
}
对于给定数组,求解第 k大元素,且要求线性复杂度,正解为使用「快速选择」做法。
基本思路与「快速排序」一致,每次敲定一个基准值 x
,根据当前与 x
的大小关系,将范围在 的 划分为到两边。
同时利用,利用题目只要求输出第 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);
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.215
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有