经典面试题目——TopK问题

爱被打了一巴掌 2024-04-23 15:31 69阅读 0赞

**目录**

一、什么是TopK问题？

二、解决思路是什么？

三、代码实现

四、OJ实战演练

五、TopK问题扩展：求数组中第k大的元素

--------------------

![0db90846b8194ddd9bcdab6251ad3e73.jpeg][]

## 一、什么是TopK问题？ ##

> ?TOP-K问题：**即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。**
> 
> 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

## 二、解决思路是什么？ ##

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，

> ?有小伙伴可能就会这样干：比如要求数组中前k个最大的元素，那么就把该数组建立为大根堆（此时堆顶元素不就是当前数组中最大的吗）
> 
> ?**然后不就可以不断的弹出当前堆顶元素，同时不断的更新堆顶以及保证当前堆一直是大根堆。像这样我们所弹出的K个元素不就是数组前k个最大元素吗？**

于是我们写出来这样的代码：

/**
         * topK问题，找出数组中最大的k个元素， 但这不是最优的解决方案
         * 时间复杂度：O(N * logn), 想一下他的空间复杂度的是多少，是O(n)吗？
         * @param array
         * @return 前k个元素所组成的数组
         */
        public static int[] topK1(int[] array, int k) {
            IntCmp intCmp = new IntCmp(); // 自定义的比较器，用来实现大根堆（因为PriorityQueue的排序方法默认实现小根堆）
            // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(intCmp);
            for (int i = 0; i < array.length; i++) {
                priorityQueue.offer(array[i]); // 每插入一个元素就要向上调整一次，时间复杂度：n * logn
            }
            // 程序走到这里我们已经构建了一个大根堆
            int[] ret = new int[k];
            for (int i = 0; i < k; i++) {
                ret[i] = priorityQueue.poll(); // 每弹出一个堆顶元素就要向下调整一次，时间复杂度：n * logn
            }
            return ret;
        }
    
        // 自定义了一个比较器对象，完成大根堆的构建
    class IntCmp implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }

**这样做当然可以但不是最优的解决方法 ?**

最优的解决思路如下：

> 基本思路如下：  
> 1. **用数据集合中前K个元素来建堆**  
> 求前k个最大的元素，则建小堆  
> 求前k个最小的元素，则建大堆
> 
>   
> 2. **用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素**  
> 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素  
>

## 三、代码实现 ##

>     import java.util.Arrays;
>     import java.util.Comparator;
>     import java.util.PriorityQueue;
>     
>     public class Test1 {
>     /**
>          * topK问题，最优解法
>          * @return 堆中前k个最大的元素所组成的数组
>          */
>         public static int[] topK(int[] array, int k) {
>             // 要求堆中前k个最大元素，先将数组中前k个元素建成小根堆（如果要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的）
>             // 创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序 。默认的排序方法建成的是小根堆）
>             PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
>             for (int i = 0; i < k; i++) {
>                 priorityQueue.offer(array[i]);
>             }
>             // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较
>             // 如果当前i下标的元素比堆顶元素大，就删除堆顶元素，并把i下标的元素放到堆中
>             for (int i = k; i < array.length; ++i) {
>                 if (array[i] > priorityQueue.peek()) {
>                     priorityQueue.poll();
>                     priorityQueue.offer(array[i]);
>                 }
>             }
>             int[] ret = new int[k];
>             for (int i = 0; i < k; i++) {
>                 ret[i] = priorityQueue.poll();
>             }
>             return ret;
>         }
>         // 主函数，程序的入口
>         public static void main(String[] args) {
>             int[] a = {23, 42, 23, 32, 12};
>             int[] ret = topK(a,2);
>             System.out.println("数组中前两个最大的元素是："+ Arrays.toString(ret));
>         }
>     }

![6a78ddf524104cbfb0c2171504dc7a7f.png][]

## 四、OJ实战演练 ##

![0e9f30a8e1014143bf57bd1f13cfe4a7.png][]

思路：直接套用我们刚才的TopK求解方法就好

**?代码实现**

>     class Solution {
>         class IntCmp implements Comparator<Integer> {
>         @Override
>         public int compare(Integer o1, Integer o2) {
>             return o2 - o1; // 构建大根堆
>         }
>     }
>         public int[] smallestK(int[] array, int k) {
>             if (k == 0) return new int[0];
>             // 要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的
>             // 创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序 。默认的排序方法建成的是小根堆）
>             IntCmp intCmp = new IntCmp();
>             PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(intCmp);
>             for (int i = 0; i < k; i++) {
>                 priorityQueue.offer(array[i]);
>             }
>             // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较
>             // 如果当前i下标的元素比堆顶元素小，就删除堆顶元素，并把i下标的元素放到堆中
>             for (int i = k; i < array.length; ++i) {
>                 if (array[i] < priorityQueue.peek()) {
>                     priorityQueue.poll();
>                     priorityQueue.offer(array[i]);
>                 }
>             }
>             int[] ret = new int[k];
>             for (int i = 0; i < k; i++) {
>                 ret[i] = priorityQueue.poll();
>             }
>             return ret;
>         }
>     }

--------------------

## 五、TopK问题扩展：求数组中第k大的元素 ##

**思路：**

在求堆中前K个最大元素的过程中，最后得到的堆顶元素就是第K大的元素

**?代码实现**

// 获取当前数组中第K大的元素
        public static int getK(int[] array, int k) {
            // 要求堆中前k个最大元素，先将数组中前k个元素建成小根堆（如果要求堆中前k个最小元素，先将数组中前k个元素建成大根堆，正好是反过来的）
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
            for (int i = 0; i < k; i++) {
                priorityQueue.offer(array[i]);
            }
            // 遍历剩下的array.length - k个元素，从数组的第k + 1个元素开始，剩下的每个元素都和当前堆顶元素进行比较
            // 如果当前i下标的元素比堆顶元素大，就删除堆顶元素，并把i下标的元素放到堆中
            for (int i = k; i < array.length; ++i) {
                if (array[i] > priorityQueue.peek()) {
                    priorityQueue.poll();
                    priorityQueue.offer(array[i]);
                }
            }
            // 程序运行到了这里，我们的优先级队列里（堆中）存放的就是堆中前k个最大的元素，此时堆顶元素就是第k大的元素
            return priorityQueue.peek();
        }

[0db90846b8194ddd9bcdab6251ad3e73.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3423985d44b2496394e896687d7f9307.jpeg
[6a78ddf524104cbfb0c2171504dc7a7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f00ece19eebe4d34bfb386385f67ad1d.png
[0e9f30a8e1014143bf57bd1f13cfe4a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f285f48fc7c44d9a8ddbe5f353086788.png