面试题 : Top-k问题

这篇具有很好参考价值的文章主要介绍了面试题 : Top-k问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

简介

题目

示例

提示

开始解题

1.思路

2.解题代码

3.时间复杂度

4.运行结果

​编辑

目前问题

真正的解法

1.以找前K个最大的元素为例

2.代码执行过程&&时间复杂度的计算

3.画图演示代码执行过程

4.解题代码

两种解法的比较

完结撒花✿ヽ(°▽°)ノ✿


面试题 : Top-k问题,刷题专栏,java,javascript,前端

 文章来源地址https://www.toymoban.com/news/detail-659754.html

博主推荐:毕竟面试题,还是动动你们的小手收藏一下,万一以后面试的时候遇到了,就赚到了!o(* ̄︶ ̄*)o

简介

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

  • 前k个最大的元素,则建小堆
  • 前k个最小的元素,则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素

题目

设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例

输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4
]

提示

  •   0 <= len(arr) <= 100000 
  •   0 <= k <= min(100000, len(arr))

开始解题

1.思路

  1. 建立小根堆,遍历这个数组把数组中的元素都放到小根堆中
  2. 定义一个数组ret作为返回值,,取k次堆顶元素放到数组中,返回ret

2.解题代码

public class Solution {
    /*
     * 这样写的话效率不是很高
     * */
    public int[] smallestK(int[] arr, int k) {
        int[] ret= new int[k];
        if(arr==null||k==0){
            return null;
        }
        //向上调整来建堆,时间复杂度为 O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int i : arr) {
            minHeap.offer(i);
        }
        //poll() 移除优先级最高的元素并返回,如果优先级队列为空,返回null
        //每一次移除堆顶元素,都必须进行向下调整这棵二叉树,假设树的高度为h,时间复杂度log(h)
        //再加上循环k次,这段代码的时间复杂度为O(K * logH)
        for (int i = 0; i < k; i++) {
            ret[i]=minHeap.poll();
        }
        return ret;
    }
}

3.时间复杂度

        //向上调整来建堆,时间复杂度为 O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int i : arr) {
            minHeap.offer(i);
        }
        //poll() 移除优先级最高的元素并返回,如果优先级队列为空,返回null
        //每一次移除堆顶元素,都必须进行向下调整这棵二叉树,假设树的高度为h,时间复杂度log(h)
        //再加上循环k次,这段代码的时间复杂度为O(K * logH)
        for (int i = 0; i < k; i++) {
            ret[i]=minHeap.poll();
        }

 所以上述解法的时间复杂度为:O(N*logN+K * logH)

4.运行结果

面试题 : Top-k问题,刷题专栏,java,javascript,前端

目前问题

代码运行效率不高,时间复杂度不行,太高了

       主要原因

        //向上调整来建堆,时间复杂度为 O(N*logN)
        Queue<Integer> minHeap = new PriorityQueue<>();
        for (int i : arr) {
            minHeap.offer(i);
        }
        //poll() 移除优先级最高的元素并返回,如果优先级队列为空,返回null
        //每一次移除堆顶元素,都必须进行向下调整这棵二叉树,假设树的高度为H,由节点总数与树的高度关系可得:N=2^H-1=>H=log(N+1)
        //再加上循环k次,这段代码的时间复杂度为O(K*logN)
        for (int i = 0; i < k; i++) {
            ret[i]=minHeap.poll();
        }


真正的解法

TOP-K问题:即求数据集合中前K个最大的元素或者最小的元素

TOP-K问题并不是将全部数据建立成堆,因为TOP-K问题一般情况下数据量都比较大。

真正的解法:是拿前K个建堆;找前K个最小的元素,建一个大根堆;找前K个最大的元素,建一个小根堆

TOP-K主要指的是在很大的一组数据的背景下进行,前K个元素仅仅只占很小的一部分,所以建堆和调整堆的时间复杂度也就变得很小了

1.以找前K个最大的元素为例

输入: arr = [27,15,19,18,28], k = 3

2.代码执行过程&&时间复杂度的计算

1.建立一个大小为K的小根堆(构造器默认的),没放元素,本质上是建立了一个大小为K的数组

2.遍历数组的前K个,放到小根堆minHeap当中 => 向上调整建堆
   时间复杂度: K*logK

3.遍历剩下的K-1个,每次和堆顶元素进行比较
   (1)如果该元素比堆顶元素小说明该元素一定不是前K个最大元素中的值,就不入堆;
   (2)如果该元素比堆顶元素大堆,则该元素与堆中最后个元素交换,再移除最后一个元素再把该元素入堆,
       入到最后一个先素的位置,调整该完全二叉树,使其再次成为个小根堆;
   时间复杂度:(N-K)*H=>(N-K)logK   注:(H为树的高度,K=2^H-1,H=log(K+1))
   (N-K)*H=>(N-K)*log(K+1)=>(N-K)logK

4.将堆中的元素放到ret里面,每次poll都是弹出堆中的最小值
   时间复杂度: K*logK

所以时间复杂度: K*logK+(N-K)*logK+ K*logK => N*logK + K*logK
   取近似值:O(N*logK)  注:K为常数,可忽略不计

3.画图演示代码执行过程

面试题 : Top-k问题,刷题专栏,java,javascript,前端

 注:

  • 小根堆中是前K个最大的值
  • 堆顶元素是这K个最大的值里面最小的
  • 最后的堆顶元素就是第K大的元素(牢记,面试官可能会问到!!!)
  • 当遍历到数组元素大于堆顶的时候,说明此时堆顶的元素一定不是前K个最大的值

4.解题代码

    /*
    * 前k个最大的元素
    * 时间复杂度:K*logK
    * */
    public static int[] largestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr==null||k==0){
            return null;
        }
        //1.建立一个大小为K的小根堆(构造器默认的),没放元素,本质上是建立了一个大小为K的数组

        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //2.遍历数组的前K个,放到小根堆minHeap当中
        //时间复杂度: K*logK+(N-K)logK+ K*logK
        //取近似值:O(N*logK)
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
      /* 3.遍历剩下的K-1个,每次和堆顶元素进行比较
        (1)如果该元素比堆顶元素小说明该元素一定不是前K个最大元素中的值,就不入堆;
        (2)如果该元素比堆顶元素大堆,则该元素与堆中最后个元素交换,再移除最后一个元素再把该元素入堆,
        入到最后一个先素的位置,调整该完全二叉树,使其再次成为个小根堆*/
        //时间复杂度:(N-K)*H=>(N-K)logK
        //注:(H为树的高度)K=2^H-1,H=log(K+1)
        //(N-K)*H=>(N-K)*log(K+1)=>(N-K)logK
        for (int i = k; i <arr.length ; i++) {
            int heapTop = minHeap.peek();
            if (arr[i]>heapTop){
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //4.将堆中的元素放到ret里面,每次poll都是弹出堆中的最小值
        //时间复杂度: K*logK
        for (int i = 0; i < k; i++) {
            ret[i]=minHeap.poll();
        }
        return ret;
    }

两种解法的比较

第一种解法时间复杂度为:O(N*logN+K * logN)

第二种解法时间复杂度为:O(N*logK)

注:K是常数,且数值与N相比极小

第二种解法远远优于第一种解法,面试官看到会给你竖起大拇指的

完结撒花✿✿ヽ(°▽°)ノ✿✿

面试题 : Top-k问题,刷题专栏,java,javascript,前端

 

 

 

 

 

 

 

到了这里,关于面试题 : Top-k问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 | TOP-K问题

    TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。 就是从N个数里面找最大前K个(N远大于K) 思路一: N个数插入到堆里面,PopK次 时间复杂度是 O(N*logN) + K*logN == O(N*logN) N很大很大,假设N是100亿,K是10 100亿个整数大概需要40G左右 所以

    2024年02月05日
    浏览(40)
  • 数据结构与算法:堆排序和TOP-K问题

    朋友们大家好,本节内容来到堆的应用:堆排序和topk问题 我们在c语言中已经见到过几种排序,冒泡排序,快速排序(qsort) 冒泡排序的时间复杂度为O(N 2 ),空间复杂度为O(1);qsort排序的时间复杂度为 O(nlogn),空间复杂度为O(logn),而今天所讲到的堆排序在时间与空间复杂度上相

    2024年03月08日
    浏览(58)
  • 什么是堆,如何实现?(附堆排序,TOP-K问题)

    欢迎来到 Claffic 的博客   💞💞💞 “春风里,是谁 花一样烂漫?” 前言: 二叉树给大家讲解的差不多了,接下来就是二叉树的实际应用了:这期我们来讲堆,它是一种顺序结构的特殊二叉树,可以实现排序等功能,那就让我们开始吧! 目录 🌸Part1: 何为堆 1.堆的概念 2.堆

    2023年04月11日
    浏览(34)
  • 【JavaDS】优先级队列(PriorityQueue),堆,Top-k问题

    ✨ 博客主页: 心荣~ ✨ 系列专栏: 【Java实现数据结构】 ✨ 一句短话: 难在坚持,贵在坚持,成在坚持! 如果有一个 关键码的集合K = {k0,k1, k2,…,kn-1} ,把它的所有元素 按完全二叉树的顺序存储方式存储 在一 个一维数组中 ,并满足: Ki = K2i+1 且 Ki= K2i+2 (Ki = K2i+1 且 Ki = K2i

    2024年02月01日
    浏览(44)
  • 【数据结构】堆的实现,堆排序以及TOP-K问题

    目录 1.堆的概念及结构 2.堆的实现 2.1初始化堆 2.2销毁堆 2.3取堆顶元素 2.4返回堆的大小 2.5判断是否为空 2.6打印堆 2.7插入元素 2.8堆的向上调整 2.9弹出元素 2.10堆的向下调整 3. 建堆时间复杂度 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 堆是一种数据结构,它是由一组元素组成的,并

    2024年02月12日
    浏览(50)
  • 堆(两种建堆方法)、堆排序和Top-K问题

    是一种完全二叉树,分为大堆,小堆 如果有一个关键码的集合 int K[ ] = {27,15,19,18,28,34,65,49,25,37} ; 把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:K i =K 2*i+1 且K i =K 2*i+2 ( K i =K 2*i+1 且K i =K 2*i+2 ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大

    2023年04月09日
    浏览(31)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(44)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(41)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(51)
  • 数据结构-堆的实现及应用(堆排序和TOP-K问题)

    1.堆的知识点: 下面我们通过一张图片来更加深刻地理解堆 上面我们说过,堆的物理结构是一个数组,逻辑结构是一个完全二叉树,所以堆的实际结构类似于顺序表,只不过我们的处理方式类似于二叉树 那么我们就可以用顺序表那样的结构来表示堆了 于是我们可以写出这样的代码

    2024年02月07日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包