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 条评论
登录 后参与评论

相关文章

  • LeetCode215.数组中的第K个最大元素

    mathor
  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • 搜索(4)

    mathor
  • LeetCode215.数组中的第K个最大元素

    mathor
  • loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

    我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

    attack
  • 选择排序

    #include<stdio.h> void SelectSort(int n,int a[]) { for(int i=0; i<n; i++) ...

    用户1624346
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • 探索C++对象模型

    只说C++对象模型在内存中如何分配这是不现实的,所以这里选择VS 2013作为调试环境具体探讨object在内存中分配情况.目录给出了具体要探讨的所有模型,正...

    racaljk
  • 算法导论第二章小试牛刀

    Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

    CloudDeveloper
  • 排序一栏(总结帖)

          学了很多的排序,基数排序,堆排序,希尔排序,选择排序,归并排序,快速排序,冒泡排序.....等等,尽管网上好文,如堆山之牛毛,但是还是没有自己写,来...

    Gxjun

扫码关注云+社区

领取腾讯云代金券