面试必问:找出一组数中最小的K个数(海量数据Top K问题)

题目

输入 n 个整数,找出其中最小的 k 个数。例如输入4、5、1、6、2、7、3、8 这8个数字,则最小的4个数字是1、2、3、4。

初窥

这道题最简单的思路莫过于把输入的 n 个整数排序,排序之后位于最前面的 k 个数就是最小的 k 个数。这种思路的时间复杂度是 O(nlogn)。

解法一:脱胎于快排的O(n)的算法

如果基于数组的第 k 个数字来调整,使得比第 k 个数字小的所有数字都位于数组的左边,比第 k 个数字大的所有数字都位于数组的右边。这样调整之后,位于数组中左边的 k 个数字就是最小的 k 个数字(这 k 个数字不一定是排序的)。下面是基于这种思路的参考代码:

public class LeastK {

    public static void getLeastNumbers(int[] input, int[] output) {
        if (input == null || output == null || output.length <= 0 || input.length < output.length) {
            throw new IllegalArgumentException("Invalid args");
        }

        int start = 0;
        int end = input.length - 1;
        int index = partition(input, start, end); //切分后左子数组的长度
        int target = output.length - 1; //K-1

        //若切分后左子数组长度不等于K
        while (index != target) {
            //若切分后左子数组长度小于K,那么继续切分右子数组,否则继续切分左子数组
            if (index < target) {
                start = index + 1;
            } else {
                end = index - 1;
            }
            index = partition(input, start, end);
        }

        System.arraycopy(input, 0, output, 0, output.length);
    }

    private static int partition(int arr[], int left, int right) {
        int i = left;
        int j = right + 1;
        int pivot = arr[left];

        while (true) {
            //找到左边大于pivot的数据,或者走到了最右边仍然没有找到比pivot大的数据
            while (i < right && arr[++i] < pivot) { //求最大的k个数时,arr[++i] > pivot
                if (i == right) {
                    break;
                }
            }
            //找到右边小于pivot的数据,或者走到了最左边仍然没有找到比pivot小的数据
            while (j > left && arr[--j] > pivot) { //求最大的k个数时,arr[--j] < pivot
                if (j == left) {
                    break;
                }
            }
            //左指针和右指针重叠或相遇,结束循环
            if (i >= j) {
                break;
            }
            //交换左边大的和右边小的数据
            swap(arr, i, j);
        }
        //此时的 a[j] <= pivot,交换之
        swap(arr, left, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

采用上面的思路是有限制的,比如需要修改输入的数组,因为函数 Partition 会调整数组中的顺序,当然了,这个问题完全可以通过事先拷贝一份新数组来解决。值得说明的是,这种思路是不适合处理海量数据的。若是遇到海量数据求最小的 k 个数的问题,可以使用下面的解法。

解法二:适合处理海量数据的O(nlogk)的算法

我们可以先创建一个大小为K的数据容器来存储最小的 k 个数字,接下来我们每次从输入的 n 个整数中读入一个数。如果容器中已有的数字少于 k 个,则直接把这次读入的整数放入容器之中;如果容器中已有 k 个数字了,也就是容器已满,此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的 k 个数中的最大值,然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小,则用这个数替换当前已有的最大值;如果待插入的值比当前已有的最大值还要大,那么这个数不可能是最小的 k 个整数之一,于是我们可以抛弃这个整数。

因此当容器满了之后,我们要做 3 件 事情:一是在 k 个整数中找到最大数;二是有可能在这个容器中删除最大数;三是有可能要插入一个新的数字。如果用一个二叉树来实现这个数据容器,那么我们能在O(logk)时间内实现这三步操作。因此对于 n 个输入数字而言,总的时间效率就是O(nlogk)。

我们可以选择用不同的二叉树来实现这个数据容器。由于每次都需要找到 k 个整数中的最大数字,我们很容易想到用最大堆。在最大堆中,根结点的值总是大于它的子树中任意结点的值。于是我们每次可以在 O(1) 得到已有的 k 个数字中的最大值,但需要 O(logk) 时间完成删除及插入操作。

我们自己从头实现一个最大堆需要一定的代码,这在面试短短的几十分钟内很难完成。我们还可以采用 Java 提供的具有优先级的队列来实现我们的容器。

public class LeastK {

    public static Integer[] getLeastNumbers(int[] nums, int k) {
        // 默认自然排序,需手动转为降序
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2) {
                    return -1;
                } else if (o1 < o2) {
                    return 1;
                }
                return 0;
            }
        });
        for (int num : nums) {
            if (maxQueue.size() < k || num < maxQueue.peek()) { // peek():返回队列头部的值,也就是队列最大值
                // 插入元素
                maxQueue.offer(num);
            }
            if (maxQueue.size() > k) {
                // 删除队列头部
                maxQueue.poll();
            }
        }
        return maxQueue.toArray(new Integer[0]);
    }

}

海量数据Top K

Top K 问题是在面试中经常被问到的问题,比如:从20亿个数字的文本中,找出最大的前100个。

若是遇到此类求海量数据中最大的 k 个数的问题,可以参考上面的求最小的 k 个数,改用最小堆,实现如下的 Java 代码:

public class TopK {

    public Integer[] getLargestNumbers(int[] nums, int k) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); // 默认自然排序
        for (int num : nums) {
            if (minQueue.size() < k || num > minQueue.peek()) { // peek():返回队列头部的值,也就是队列最小值
                // 插入元素
                minQueue.offer(num);
            }
            if (minQueue.size() > k) {
                // 删除队列头部
                minQueue.poll();
            }
        }
        return minQueue.toArray(new Integer[0]);
    }

}

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊nacos config的publishConfig

nacos-1.1.3/config/src/main/java/com/alibaba/nacos/config/server/controller/Conf...

13300
来自专栏Jerry的SAP技术分享

SAP UI5 app view router - Haiji's application

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

10920
来自专栏码客

maven常用的jar

8430
来自专栏泰斗贤若如

我们一起学Python之——认识Python"规则"

开学后,跟预想的一样,开学第一天我们就开了Python,虽然之前早就预料到了,但对于一直学Java的我来说,内心还是有一些涟漪的。总归还是要接受的,还不如振作...

5810
来自专栏微信公众号【Java技术江湖】

走进JavaWeb技术世界4:Servlet 工作原理详解

本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

8300
来自专栏程序员的梦想

超详细:6种常用的设计模式总结

简单点说,就是一个应用程序中,某个类的实例对象只有一个,你没有办法去new,因为构造器是被private修饰的,一般通过getInstance()的方法来获取它...

8200
来自专栏软件测试testclass

Jmeter基于windows性能测试环境搭建

Apache JMeter™应用程序是开放源码软件,是一个100%纯Java应用程序,用于加载测试功能行为和度量性能。它最初是为测试Web应用程序而设计的,但后...

8630
来自专栏微信公众号【Java技术江湖】

走进JavaWeb技术世界5:初探Tomcat的HTTP请求过程

本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

12100
来自专栏微信公众号【Java技术江湖】

走进JavaWeb技术世界6:Tomcat5总体架构剖析

本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

6700
来自专栏程序员的梦想

一起来看一下Java中的Annotation注解

我们在平时的开发过程中看到很多如@Override,@SuppressWarnings,@Test等样式的代码就是注解,注解是放到类、构造器、方法、属性、参数前...

8500

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励