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