点击 这里 可以查看更多算法面试相关内容~
题目描述
这是 LeetCode 上的703. 数据流中的第 K 大元素，难度为 Easy。
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例：
输入： ["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 复制代码
提示：
1 <= k <= 10^40 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4-10^4 <= val <= 10^4最多调用 add 方法 10^4 次题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素
冒泡排序解法（TLE）
每次调用 add 时先将数装入数组，然后遍历 k 次，通过找 k 次最大值来找到 Top K。
class KthLargest { int k; List<Integer> 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); } } 复制代码
- 时间复杂度：O(nk)O(nk)O(nk)
- 空间复杂度：O(n)O(n)O(n)
快速排序解法
上述的解法时间复杂度是 O(nk)O(nk)O(nk) 的，当 k 很大的时候会超时。
我们可以使用快排来代替冒泡。
将复杂度变为 O(nlogn)O(n\log{n})O(nlogn)，不能说 O(nlogn)O(n\log{n})O(nlogn) 复杂度一定比 O(nk)O(nk)O(nk) 要低，但 O(nlogn)O(n\log{n})O(nlogn) 通常更加接近 O(n)O(n)O(n)。
本题的 n 的范围是 10410^4104，O(nlogn)O(n\log{n})O(nlogn) 解法的效率等于一个常数为 15 以内的 O(n)O(n)O(n) 算法：
class KthLargest { int k; List<Integer> 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); } } 复制代码
- 时间复杂度：O(nlogn)O(n\log{n})O(nlogn)
- 空间复杂度：O(n)O(n)O(n)
优先队列解法
使用优先队列构建一个容量为 k 的小根堆。
将 nums 中的前 k 项放入优先队列（此时堆顶元素为前 k 项的最大值）。
随后逐项加入优先队列：
- 堆内元素个数达到
k个：
- 加入项小于等于堆顶元素：加入项排在第
k大元素的后面。直接忽略 - 加入项大于堆顶元素：将堆顶元素弹出，加入项加入优先队列，调整堆
- 堆内元素个数不足
k个，将加入项加入优先队列
将堆顶元素进行返回（数据保证返回答案时，堆内必然有 k 个元素）：
class KthLargest { int k; PriorityQueue<Integer> 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(); } } 复制代码
- 时间复杂度：最坏情况下，
n个元素入堆，都触发堆调整。复杂度为 O(nlogk)O(n\log{k})O(nlogk) - 空间复杂度：O(k)O(k)O(k)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
