BFPRT算法

从无序数组中找出第K大（小）的数。
一般思路：

  1. 利用partition算法。O（N），基于概率。
  2. 维护一个小（大）顶堆

BFPRT流程

  • 将数组分组，如5个数分一组
  • 组内排序
  • 将每个组的中位数（偶数拿上中位数）拿出来组成新数组，长度为N/5
  • 新数组递归上述流程，k=newArray.length()/2，得到新数组中位数(第一半小的数)num
  • 以num为支点，选择左边或右边继续BFPRT或者返回num

解决了什么：partition中支点选择问题，保证支点为中位数左右

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • bfprt算法
    前言 在一个数组中求其第k大或者第k小的数的问题(其实就是找按降序或升序排好序的数组的下标为k-1的元素)，简称T...
    topshi阅读 1,885评论 0赞 2
  • JavaScript BFPRT 算法
    BFPRT 算法 背景 在一组数中求其前 k 小的数，简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是...
    coolheadedY阅读 477评论 0赞 1
  • BFPRT算法：求第K小或者第K大的数
    问题： 一个数组中求第k小或者第k大的数 思路（转自http://blog.csdn.net/liuxiao214...
    一凡呀阅读 2,086评论 0赞 0
  • BFPRT算法O(n)解决第k小(第k大)的数
    第k小算法 我们通常会简单地进行一个快速排序后，得到第k个位置上的数字即可。我们都知道的是快速排序是个不稳定的排序...
    淌水希恩阅读 823评论 0赞 0
  • BFPRT算法O(n)解决第k小的数
    第k小算法 我们通常会简单地进行一个快速排序后，得到第k个位置上的数字即可。我们都知道的是快速排序是个不稳定的排序...
    Forget_ever阅读 5,600评论 3赞 5