BFPRT算法

说明

 在线性时间复杂度内找到数组中第k小的数字

算法流程

 首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行partition操作,也就是,把大于这个数的放左边,等于这个数的放中间,大于这个数的放右边,partition返回的是一个数组range,range[0]的值表示等于这个数的区域的左边下标值,range[1]的值表示等于这个数的区域的右边下标值。如果k在这两个下标内,那就直接返回这个数,否则,如果k<range[0],表示应该将小于区域再次进行划分;如果k>range[1],表示应该将大于区域再次进行划分。

代码

public static int getMinKthByBFPRT(int[] arr,int k) {
    int[] copyArr = new int[arr.length];
    copyArr = copyArray(arr);
    return bfprt(copyArr,0,copyArr.length - 1,k - 1);
}
    
public static int[] copyArray(int[] arr) {
    int[] tmp = new int[arr.length];    
    for(int i = 0;i != arr.length;i++) 
        tmp[i] = arr[i];
    return tmp;
}
    
public static int bfprt(int[] arr,int begin,int end,int i) {//begin到end范围内求第i小的数
    if(begin == end)
        return arr[begin];
    int pivot = medianOfMedians(arr,begin,end);//中位数作为划分值
    int[] pivotRange = partition(arr,begin,end,pivot);//进行划分,返回等于区域
    if(i >= pivotRange[0] && i <= pivotRange[1]) 
        return arr[i];
    else if(i < pivotRange[0])
        return bfprt(arr,begin,pivotRange[0] - 1,i);
    else 
        return bfprt(arr,pivotRange[1] + 1,end,i);
}
    
public static int medianOfMedians(int[] arr,int begin,int end) {
    int num = end - begin + 1;
    int offset = num % 5 == 0 ? 0 : 1;
    int[] mArr = new int[num / 5 + offset];
    for(int i = 0; i < mArr.length;i++) {
        int beginI = begin + i * 5;
        int endI = beginI + 4;
        mArr[i] = getMedian(arr,beginI,Math.min(end,endI));
    }
    return bfprt(mArr,0,mArr.length - 1,mArr.length / 2);
}
    
public static int getMedian(int[] arr,int begin,int end) {
    Arrays.sort(arr,begin,end);
    int sum = end + begin;
    int mid = (sum / 2) + (sum % 2);
    return arr[mid];
}
    
public static int[] partition(int[] arr,int begin,int end,int pivotValue) {
    int small = begin - 1;
    int cur = begin;
    int big = end + 1;
    while(cur != big) {
        if(arr[cur] < pivotValue)
            swap(arr,++small,cur++);
        else if(arr[cur] > pivotValue)
            swap(arr,cur,--big);
        else 
            cur++;
    }
    int[] range = new int[2];
    range[0] = small + 1;
    range[1] = big - 1;
    return range;
}

public static void swap(int[] arr,int i,int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

总结

 这个算法为什么能达到O(n)的时间复杂度,假设直接随机选一个数,进行partition操作,最差情况会分的很不均匀(大于,等于,小于区域),导致时间复杂度会退化为O(n^2^),但是BFPRT算法利用了取中位数的思想,可以保证取出的数x,至少有3/10的数大于x,3/10的数小于x,因此会将区域分的比较均匀,时间复杂度达到O(n)

例题

LeetCode215

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

4176
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

701
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

4697
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

3192
来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

1734
来自专栏chenjx85的技术专栏

leetcode-633-Sum of Square Numbers

1452
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法(下)

昨天发表的java常用排序算法/程序员必须掌握的8大算法(上),没看的可以点上面这个链接↑↑↑↑,(概念+实例+代码+排序舞蹈视频)更好的帮助你理解。 java...

4709
来自专栏数据结构与算法

深海中的STL—nth_element

如果让你求区间第k大,你会怎么做呢? 主席树?确实是个不错的选择(不过像我这种垃圾还是乖乖打暴力吧) 在c++的stl库中,提供了nth_element...

3847
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3434
来自专栏无所事事者爱嘲笑

常用的sort打乱数组方法真的有用?

2686

扫码关注云+社区

领取腾讯云代金券