海量数据-两种方法解决top k问题

假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素?

最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取top k,时间成本也就是排序成本了,为O(nlogn),而这里的n是百万级别的,那能不能更快一点呢?

最小堆

假设我们设定一个最小堆,并固定这个最小堆的最大大小为k,那么任何一时刻堆顶元素都是这个堆中的第k大的数据(也是最小的数据)。来一个数据就和堆顶元素比较,如果比堆顶元素大就替换堆顶元素,并堆化。最后当所有数据都走一遍后,堆内的元素就是所有数据中最大的k个元素,而堆顶元素就是第k大的元素。

那么我们来分析一下它在时间复杂度上优化了多少吧。首先所有数据都要走一遍比较,就是n,其次维护了一个大小为k的堆,也就是说堆化的时间复杂度为O(log k),那么总的时间复杂度就是O(nlogk) ,乍一看和先排序的时间复杂度O(nlogn)也没差多少,甚至说是一个衡量级别的,但毕竟这里说的是海量数据,n可能很大,k可能比较小,那么时间上就快很多了。

它的另一个好处是空间复杂度也仅为O(k),不需要额外维护一个O(n)级别的海量数据存储。

代码实现:

public static List<Integer> topKByHeap(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
        return new ArrayList<>();
    }
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i = 0; i < k; i++) {
        minHeap.add(arr[i]);
    }
    for (int i = k; i < arr.length; i++) {
        if (arr[i] > minHeap.peek()) {
            minHeap.poll();
            minHeap.add(arr[i]);
        }
    }
    return new ArrayList<>(minHeap);
}

快排思想

海量数据-两种方法解决top k问题

O(nlogk)好像还是有点不够看,能不能直接优化成O(n)呢?

我们知道快排的思想是每次随机选取一个pivot把数组划分成相对有序的两部分,那假设第一次随机选取pivot并分区之后,后面这部分的元素数量就正好为k,不就说明后面这部分数据就是最大的k个元素,那最好时间复杂度岂不是O(logn)

海量数据-两种方法解决top k问题

那么问题就成为了选中一个pivot,将数组分为前后两部分,后面部分元素的数量为k的问题。

虽然很难一次就中,但我们在一次分区后,通过比较k和后面部分元素的数量就知道了,后面部分的元素是分多了还是分少了。

如果后面的元素数量分多了,就继续在后面这部分数据中随机选取pivot,重复步骤。如果后面的元素分少了,则往前选取pivot,就形成了一种类似二分查找的步骤。

那么我们来分析一下它的时间复杂度,我们知道快速排序每次分区的时间复杂度就是log(n),那么我们假设每次分区前后两部分的数量相近,那么时间复杂度就是log(n)+log(n/2)+log(n/4)+...,取极限为log(2n),即log(n)级别,是不是比一开始的log(nlogn)快很多?特别是在海量数据的情况下。

代码实现:

public static List<Integer> topK(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
        return new ArrayList<>();
    }
    // 如果是 BottomK 的话就不需要单独处理 k==n 情况了,因为划分是小于等于放在左
    // topK 的话如果是将大于的 k 个放在右边,那么 pivot 就变成了-1,会形成死循环。
    if (k == arr.length) {
        return IntStream.of(arr).boxed().collect(Collectors.toList());
    }
    int low = 0;
    int high = arr.length - 1;
    int index = QuickSort.partition(arr, low, high);
    while (index != arr.length - k - 1) {
        if (index > arr.length - k - 1) {
            index = QuickSort.partition(arr, low, index - 1);
        } else {
            index = QuickSort.partition(arr, index + 1, high);
        }
    }
    List<Integer> list = new ArrayList<>(k);
    for (int i = index + 1; i < arr.length; i++) {
        list.add(arr[i]);
    }
    System.out.println(Arrays.toString(arr));
    return list;
}

这里的Quicksort得自己实现了,这里不作为重点,可以参考十大排序算法与Java实现

如果是找第K大的元素呢?

作为拓展,讨论一下如果要找第K大的数据,仍然可以用这两个方法:

  • 对于最小堆则是操作一遍之后直接取堆顶元素。
  • 对于快排思想,则是找一个pivot,使得分区之后它正好处于第arr.length-k+1的位置上。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e6%b5%b7%e9%87%8f%e6%95%b0%e6%8d%ae-%e4%b8%a4%e7%a7%8d%e6%96%b9%e6%b3%95%e8%a7%a3%e5%86%b3top-k%e9%97%ae%e9%a2%98/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月4日
下一篇 2020年4月4日

相关推荐

  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    0100
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110
  • 数组元素左右两边最近较小元素

    原题(来源牛客网) 给定一个不含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例: 输入: ar…

    算法 2020年4月26日
    0700
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0220
  • leetcode71-简化路径

    原题 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..…

    算法 2020年1月23日
    090
  • 剑指offer35-复杂链表的复制

    原题(来源Leetcode) 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random …

    2020年6月13日
    0110
  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04580
  • leetcode151-翻转字符串里的单词

    原题 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he…

    算法 2019年11月22日
    090
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0250

发表回复

登录后才能评论