如何解决TOP-K问题

前言:最近在开发一个功效:动态展示的订单数目排名前10的都会,这是一个典型的Top-k问题,其中k=10,也就是说找到一个聚集中的前10名。现实生活中Top-K的问题异常普遍,好比:微博热搜的前100名、抖音直播的小时榜前50名、百度热搜的前10条、博客园点赞最多的blog前10名,等等若何解决这类问题呢?开端的想法是将这个数据聚集排序,然后直接取前K个返回。这样解法可以,然则会存在一个问题:排序了许多不需要去排序的数据,时间复杂度过高.假设有数据100万,对这个聚集举行排序需要很长的时间,即便使用快速排序,时间复杂度也是O(nlogn),那么这个问题若何解决呢?解决方式就是以空间换时间,使用优先级行列

目录

一:  熟悉PriorityQueue
二:行使PriorityQueue解决topk问题
三:总结

 

一:熟悉PriorityQueue

1.1:PriorityQueue位于java.util包下,继续自Collection,因此它具有聚集的属性,而且继续自Queue行列,拥有add/offer/poll/peek等一系列操作元素的能力,它的默认巨细是11,底层使用Object[] 来保留元素,数组的话一定会有扩容,当添加元素的时刻巨细跨越数组的容量,就会扩容,扩容的巨细为原数组的巨细加上,若是元素的数目小于64,则每次加2,若是大于64,则每次增添一半的容量。

如何解决TOP-K问题

 1.2:PriorityQueue的组织方式

    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
 public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

对照常用的就是这两个组织方式,其中第一个组织方式中需要组织一个对照器,第二个组织方式添加初始容量和对照器,对照器可以自界说任何元素的优先级,凭据需要增添元素的优先级展示

 1.3:PriorityQueue的常用API

如何解决TOP-K问题

1.3.1:offer方式和add方式用于添加元素,本质上offer方式和add方式是相同的:

    public boolean add(E e) {
        return offer(e);
    }

 offer方式主要步骤就是判空、扩容、添加元素,添加元素的话,siftup方式里会凭据组织方式,若是有对照器就举行对照,没有对照器的话就给元素赋予对照能力,而且凭据组织的巨细,也就是

 initialCapacity举行对照,若是对照器的compare方式不相符界说的规则,直接break;相符的话会给数组的元素举行赋值

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

1.3.2:poll方式和peek方式都是返转头元素,不同之处在于poll方式会返转头顶元素而且移除元素,peek方式不会移除头顶元素:

  public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
    public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }

 二:PriorityQueue解决问题

2.1:数组的前K大值

如何解决TOP-K问题

代码:

import java.util.PriorityQueue;

public class TopK {

    //找出前k个最大数,接纳小顶堆实现
    public static int[] findKMax(int[] nums, int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<>(k);//行列默认自然顺序排列,小顶堆,不必重写compare

        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
                //若是堆顶元素 < 新数,则删除堆顶,加入新数入堆,保持堆中存储着大值
            } else if (pq.peek() < num) {
                pq.poll();
                pq.offer(num);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k && !pq.isEmpty(); i++) {
            result[i] = pq.poll();
        }
        return result;
    }
}

 测试:

 public static void main(String[] args) {
        int[] arr = new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
        System.out.println(Arrays.toString(findKMax(arr, 3)));
    }

//输出:

如何解决TOP-K问题

优先级行列是若何解决这个问题的呢?

PriorityQueue默认是小顶堆,那么什么是小顶堆?什么是大顶堆?假设有3、6、8三个数,需要存储在优先级行列里,画个图人人明白下:

如何解决TOP-K问题

 可以看出小顶堆的头顶元素存储着整个数据聚集中数字最小的元素,而大顶堆存储着整个数据聚集中数字最大的元素,也就是一个凭据升序排列,一个凭据降序排列:

架构设计:分布式服务,库表拆分模式详解

//小顶堆的构建方式:
PriorityQueue<Integer> queue = new PriorityQueue<>(k);
//这种写法等价于: 
PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
//同时等价于(lamda表达式的写法)
PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2) -> o1-o2);

 //大顶堆的构建方式:
 PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

拿测试用例这个例子来说:

构建的是指定容量的小顶堆,因此每次queue.peek()返回的是最小的数字,在遍历数组的过程中,若是遇到比该数字大的元素就将最小的数字poll(移除掉),然后将较大的元素添加到堆中,在添加进去堆中的时刻,堆同时会凭据优先级对照,将最小的元素再次放到堆顶,这样的做法就是会一直保持堆中的元素是相对较大的,同时堆顶元素是堆中最小的。

凭据测试用例给出的例子,{1, 6, 2, 3, 5, 4, 8, 7, 9} 优先级行列将会是这样转变的:(注重:本质上优先级行列的实现方式是数组,这里只是用二叉树的方式表现出来)

如何解决TOP-K问题

 

 如果该题换个角度,求泛起频率最低的元素怎么做呢?

相信你凭据上面的讲述应该也明了了:直接构建一个大顶堆,这样元素最大的值在堆顶,每次去和数组的元素的值去做对照,只要堆顶元素比数组的值小,就将堆顶元素poll出来,然后将数组的值添加进去,这样就可以一直保持聚集数组中一直是最小的k个数字。

 2.2:前k个高频元素

如何解决TOP-K问题

当k = 1 时问题很简单,线性时间内就可以解决,只需要用哈希表维护元素泛起频率,每一步更新最高频元素即可。当 k > 1 就需要一个能够凭据泛起频率快速获取元素的数据结构,这里就需要用到优先行列

首先确立一个元素值对应泛起频率的哈希表,使用 HashMap来统计,然后构建优先级行列,这里依旧是构建小顶堆,不外由于该题是盘算元素泛起的频率,因此我们需要将每个元素的频率值做对比,

需要重写优先级行列的comparator,需要手工填值:这个步骤需要 O(N)O(N) 时间其中 NN 是列表中元素个数。

第二步确立堆,堆中添加一个元素的复杂度是 O(\log(k))O(log(k)),要举行 NN 次复杂度是 O(N)O(N)。

最后一步是输出效果,复杂度为 O(k\log(k))O(klog(k)):

public int[] topK(int[] nums, int k) {
        //统计字符泛起的频率的map
        Map<Integer, Integer> count = new HashMap();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        //凭据泛起频率的map来构建k个元素的优先级行列
        PriorityQueue<Integer> heap =
                new PriorityQueue<>(k, (o1, o2) -> count.get(o1) - count.get(o2));

        for (int n : count.keySet()) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        int[] result = new int[heap.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = heap.poll();
        }
        return result;

    }

 测试:

public static void main(String[] args) {
        int[] nums = {1, 1, 1, 3, 5, 6, 5, 6, 5, 4, 7, 8};
        int[] res = new TOPK().topK(nums, 3);
        System.out.println(Arrays.toString(res));
    }

//输出

如何解决TOP-K问题

 

  对于这样的问题需要先对原数组举行处置,好比在盘算前3频率这个问题上,我们需要先盘算数组中数字泛起的频率,然后维护一个哈希表用来存储元素的频率。对于类似问题:微博热搜的前10名,那么一定需要统计搜索频次,抖音小时榜前10名,那么一定要统计要盘算时段的旁观人数,优先行列只不外是一个存储K元素的一个容器,它不卖力统计,只卖力维护一个K元素的最大或者最小堆顶,对于数据接纳什么样的优先级顺序需要自界说。

三:总结

      本篇博客主要先容了我们在现实中遇见的TOP-K问题有哪些,以及优先级行列PriorityQueue的基本原理先容,接着由易到难的解说了若何通过优先级行列PriorityQueue来解决TOP-k问题,这两个问题都对照经典。对于明白优先级行列的寄义、以及为什么它能解决该问题,想明了这点很主要。希望人人能够做到闻一知十,下次面临一致问题的时刻,能顺序解决。最少棘手的topk问题对于我们来说,有个PriorityQueue这个神兵利器,就显得很简单easy咯

最后若是对学习java有兴趣可以加入群:618626589,本群旨在打造无培训广告、无闲聊扯皮、无注水斗图的纯技术交流群,群里天天会分享有价值的问题和学习资料,迎接列位随时加入~

,

最后若是对学习java有兴趣可以加入群:618626589,本群旨在打造无培训广告、无闲聊扯皮、无注水斗图的纯技术交流群,群里天天会分享有价值的问题和学习资料,迎接列位随时加入~

原创文章,作者:dddof新闻网,如若转载,请注明出处:https://www.dddof.com/archives/24560.html