热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

算法TOPK(BFPRT算法)JAVA版本

一、背景在一大堆数中求其前k大或前k小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法&

一、背景

在一大堆数中求其前k大或前k小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为O(n)O(n)。

在首次接触TOP-K问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前k即可,但是这么做有两个问题: 
(1):快速排序的平均复杂度为O(nlogn)O(nlogn),但最坏时间复杂度为O(n2)O(n2),不能始终保证较好的复杂度。 
(2):我们只需要前k大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为k的堆,时间复杂度为O(nlogk)O(nlogk)。

那是否还存在更有效的方法呢?受到快速排序的启发,通过修改快速排序中主元的选取方法可以降低快速排序在最坏情况下的时间复杂度(即BFPRT算法),并且我们的目的只是求出前k,故递归的规模变小,速度也随之提高。下面来简单回顾下快速排序的过程,以升序为例: 
(1):选取主元(首元素,尾元素或一个随机元素); 
(2):以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边; 
(3):分别对左边和右边进行递归,重复上述过程。
原文链接:https://blog.csdn.net/laojiu_/article/details/54986553

    仅用荷兰国旗算法也能达到数学期望为O(N)的时间复杂度,但是也有可能存在O(N2)的最差情况,BFPRT就是在荷兰国旗算法的基础上,加入寻找一个好的中位数,让时间复杂度稳定在O(N)

二、算法套路

BFPRT算法套路
1. 对整个数组进行分组,每组5个数,不满5个的凑成最后一组
2.对每个组进行组内排序, 时间复杂度O(N)
    为什么时间复杂度O(N),解释:
    排序算法时间复杂度为O(NlogN), 当N等于5时候,即为O(1)
    对N/5个数组进行排序,所以时间复杂度为O(N)
3.拿出排序后的每个数组的中位数,组成一个新的N/5长度数组
4.递归掉BFPRT
5.拿到BFPRT的返回的num, 小于放左边,等于放中间,大于放右边。即快排里的荷兰国旗pattition算法。

伪代码:

int bfprt(int[] arr, int k){
    1.
    2.
    3.生成一个N/5大小的new_arr
    4.bfprt(new_arr, new_arr.length/2);
    5.
}

三、代码

public static int[] getMinKNumsByBFPRT(int[] arr, int k) {if (k <1 || k > arr.length) {return arr;}int minKth &#61; getMinKthByBFPRT(arr, k);int[] res &#61; new int[k];int index &#61; 0;for (int i &#61; 0; i !&#61; arr.length; i&#43;&#43;) {if (arr[i] &#61; pivotRange[0] && i <&#61; pivotRange[1]) {return arr[i];} else if (i pivotValue) {swap(arr, cur, --big);} else {cur&#43;&#43;;}}int[] range &#61; new int[2];range[0] &#61; small &#43; 1;range[1] &#61; big - 1;return range;}public static int getMedian(int[] arr, int begin, int end) {insertionSort(arr, begin, end);int sum &#61; end &#43; begin;int mid &#61; (sum / 2) &#43; (sum % 2);return arr[mid];}public static void insertionSort(int[] arr, int begin, int end) {for (int i &#61; begin &#43; 1; i !&#61; end &#43; 1; i&#43;&#43;) {for (int j &#61; i; j !&#61; begin; j--) {if (arr[j - 1] > arr[j]) {swap(arr, j - 1, j);} else {break;}}}}public static void swap(int[] arr, int index1, int index2) {int tmp &#61; arr[index1];arr[index1] &#61; arr[index2];arr[index2] &#61; tmp;}public static void printArray(int[] arr) {for (int i &#61; 0; i !&#61; arr.length; i&#43;&#43;) {System.out.print(arr[i] &#43; " ");}System.out.println();}public static void main(String[] args) {int[] arr &#61; { 6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9 };// sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }printArray(getMinKNumsByBFPRT(arr, 10));}

 


推荐阅读
  • 本文介绍了如何在给定的有序字符序列中插入新字符,并保持序列的有序性。通过示例代码演示了插入过程,以及插入后的字符序列。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • Java太阳系小游戏分析和源码详解
    本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践,作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构,包括工具类、常量、图片加载、面板等。通过这个小游戏的制作,读者可以巩固和应用所学的知识,如类的继承、方法的重载与重写、多态和封装等。 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • 本文介绍了一个Java猜拳小游戏的代码,通过使用Scanner类获取用户输入的拳的数字,并随机生成计算机的拳,然后判断胜负。该游戏可以选择剪刀、石头、布三种拳,通过比较两者的拳来决定胜负。 ... [详细]
  • CSS3选择器的使用方法详解,提高Web开发效率和精准度
    本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • 本文讨论了如何优化解决hdu 1003 java题目的动态规划方法,通过分析加法规则和最大和的性质,提出了一种优化的思路。具体方法是,当从1加到n为负时,即sum(1,n)sum(n,s),可以继续加法计算。同时,还考虑了两种特殊情况:都是负数的情况和有0的情况。最后,通过使用Scanner类来获取输入数据。 ... [详细]
  • 本文介绍了在Java中gt、gtgt、gtgtgt和lt之间的区别。通过解释符号的含义和使用例子,帮助读者理解这些符号在二进制表示和移位操作中的作用。同时,文章还提到了负数的补码表示和移位操作的限制。 ... [详细]
  • 本文介绍了OC学习笔记中的@property和@synthesize,包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • JavaSE笔试题-接口、抽象类、多态等问题解答
    本文解答了JavaSE笔试题中关于接口、抽象类、多态等问题。包括Math类的取整数方法、接口是否可继承、抽象类是否可实现接口、抽象类是否可继承具体类、抽象类中是否可以有静态main方法等问题。同时介绍了面向对象的特征,以及Java中实现多态的机制。 ... [详细]
  • Java String与StringBuffer的区别及其应用场景
    本文主要介绍了Java中String和StringBuffer的区别,String是不可变的,而StringBuffer是可变的。StringBuffer在进行字符串处理时不生成新的对象,内存使用上要优于String类。因此,在需要频繁对字符串进行修改的情况下,使用StringBuffer更加适合。同时,文章还介绍了String和StringBuffer的应用场景。 ... [详细]
  • JVM 学习总结(三)——对象存活判定算法的两种实现
    本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法:引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活,虽然简单高效,但无法解决循环引用的问题;可达性分析算法通过判断对象是否可达来确定存活对象,是主流的Java虚拟机内存管理算法。 ... [详细]
  • 不同优化算法的比较分析及实验验证
    本文介绍了神经网络优化中常用的优化方法,包括学习率调整和梯度估计修正,并通过实验验证了不同优化算法的效果。实验结果表明,Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ... [详细]
author-avatar
国民男神-权志龙
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有