MENU

BFPRT算法

August 12, 2018 • Read: 778 • 算法

说明

在线性时间复杂度内找到数组中第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

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 小伙子不错 小伙子不错