【Top K】问题的多种解法：冒泡排序 & 快速排序 & 优先队列 ...

宫水三叶的刷题日记

发布于 2021-02-20 09:56:27

9490

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

这是 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^4
0 <= 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(n)

快速排序解法

上述的解法时间复杂度是

O(nk)

的，当 k 很大的时候会超时。

我们可以使用快排来代替冒泡。

将复杂度变为

O(n\log{n})

，不能说

O(n\log{n})

复杂度一定比

O(nk)

要低，但

O(n\log{n})

通常更加接近

O(n)

。

本题的 n 的范围是

10^4

，

O(n\log{n})

解法的效率等于一个常数为 15 以内的

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(n\log{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(n\log{k})

空间复杂度：

O(k)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

「在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。」

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

腾讯云开发者社区

本文分享自宫水三叶的刷题日记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云开发者社区

登录后参与评论

0 条评论

热度