该文章是公众号:宫水三叶博主的文章,一位女神级别的算法大佬,文章大都是讲算法的,公众号广告基本没有,只分享算法心得,解题思路不要不要的,一句话很强,
原文链接:https://mp.weixin.qq.com/s/zVon8BE7l80-RT5bWdKCxA
这是 LeetCode 上的「703. 数据流中的第 K 大元素」,难度为 「Easy」。
设计一个找到数据流中第 k 大元素的类(class)。
注意是排序后的第 k 大元素,不是第 k 个不同的元素。
请实现 KthLargest 类:
示例:
输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:
[null, 4, 5, 5, 8, 8]
解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
提示:
每次调用 add 时先将数装入数组,然后遍历 k 次,通过找 k 次最大值来找到 Top K。
代码:
class KthLargest {
int k;
List list = new ArrayList<>(10009);
public KthLargest(int _k, int[] _nums) {
k = _k;
for (int i : _nums) list.add(i);
}
public int add(int val) {
list.add(val);
int cur = 0;
for (int i = 0; i < k; i++) {
int idx = findMax(cur, list.size() - 1);
swap(cur++, idx);
}
return list.get(cur - 1);
}
int findMax(int start, int end) {
int ans = 0, max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
int t = list.get(i);
if (t > max) {
max = t;
ans = i;
}
}
return ans;
}
void swap(int a, int b) {
int c = list.get(a);
list.set(a, list.get(b));
list.set(b, c);
}
}
上述的解法时间复杂度是 的,当 k 很大的时候会超时。
我们可以使用快排来代替冒泡。
将复杂度变为 ,不能说 复杂度一定比 要低,但 通常更加接近 。
本题的 n 的范围是 , 解法的效率等于一个常数为 15 以内的 算法:
代码:
class KthLargest {
int k;
List list = new ArrayList<>(10009);
public KthLargest(int _k, int[] _nums) {
k = _k;
for (int i : _nums) list.add(i);
}
public int add(int val) {
list.add(val);
Collections.sort(list);
return list.get(list.size() - k);
}
}
PS. Collections.sort 内部最终会调用 Arrays.sort 进行排序。而 Arrays.sort() 本身不只有「双轴快排」一种实现,在排序数量少的情况下会直接使用「冒泡排序」,这里的分析是假定了 Collections.sort 最终使用的是 Arrays.sort 的「双轴快排」。
使用优先队列构建一个容量为 k 的小根堆。
将 nums 中的前 k 项放入优先队列(此时堆顶元素为前 k 项的最大值)。
随后逐项加入优先队列:
将堆顶元素进行返回(数据保证返回答案时,堆内必然有 k 个元素)。
代码:
class KthLargest {
int k;
PriorityQueue queue;
public KthLargest(int _k, int[] _nums) {
k = _k;
queue = new PriorityQueue<>(k, (a,b)->Integer.compare(a,b));
int n = _nums.length;
for (int i = 0; i < k && i < n; i++) queue.add(_nums[i]);
for (int i = k; i < n; i++) add(_nums[i]);
}
public int add(int val) {
int t = !queue.isEmpty() ? queue.peek() : Integer.MIN_VALUE;
if (val > t || queue.size() < k) {
if (!queue.isEmpty() && queue.size() >= k) {
queue.poll();
}
queue.add(val);
}
return queue.peek();
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.703 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
页面更新:2024-03-24
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号