bfprt算法

前言

在一个数组中求其第k大或者第k小的数的问题(其实就是找按降序或升序排好序的数组的下标为k-1的元素)，简称TOP-K问题。解决TOP-K问题最有效的算法是bfprt算法，又称中位数的中位数算法，该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出。
类似题目 215. 数组中的第K个最大元素

bfprt算法

• TOP-K问题其实可以使用快排的partition来求解，通常选择开头、末尾或随机选择一个数作为轴来划分数据，但这存在一个问题就是最差情况下，算法时间复杂度会退化为。
• 而bfprt算法就是基于partition的基础上做出优化，旨在选择一个合适的枢轴，使得算法的最坏时间复杂度为。

bfprt算法的步骤：

• 选择枢轴
• partition，划分数据
• 根据partition的结果，递归

枢轴的选择

• 首先将给定数组划分为 n / 5组，每组 5个元素，若有多出不足5个的，自成一组
• 使用插入排序找到每个组的中位数，组成中位数数组medians
• 找到中位数数组medians中的中位数，以此作为枢轴去partition

    //排序，然后返回中位数
    private int getMedian(int[] nums, int begin, int end){
        for(int i = begin + 1;i <= end;i++){
            for(int j = i;j > begin && nums[j] < nums[j - 1]; j--){
                swap(nums, j ,j - 1);
            }
        }
        return nums[begin + ((end - begin) >> 1)];
    }
    private int getMedianOfMedians(int[] nums, int begin, int end){
        int num = end - begin + 1;
        int offset = num % 5 == 0 ? 0 : 1;
        int[] medians = new int[num / 5 + offset];
        for(int i = 0; i < medians.length;i++){
            int subBegin = begin + i * 5;
            int subEnd = subBegin + 4;
            medians[i] = getMedian(nums, subBegin, Math.min(subEnd, end));
        }
        //调用bfprt方法找到medians的中位数
        return bfprt(medians, 0, medians.length - 1, medians.length / 2);
    } 

partition

• partition是以某个元素(假设为pivot)为枢轴去划分数组，有两种划分方式(以从小到大为例)：

  • 划分为三部分(每次确定一个元素位置)

    
    

  • 划分为三部分(荷兰国旗问题)
    

    

一轮partition结束后，pivot就确定了它在数组中的位置。

private int[] partition(int[] nums, int begin, int end, int pivot){
        int l = begin - 1, r = end + 1;
        int i = begin;
        while(i < r){
            if(nums[i] == pivot){
                i++;
            }else if(nums[i] > pivot){
                swap(nums, ++l, i++);
            }else{
                swap(nums, i, --r);
            }
        }
        return new int[]{l + 1, r - 1};
    }

bfprt求解

bfprt算法采用分治的思想，首先找到枢轴，再partition，以荷兰国旗问题的partition为例，它返回中间部分的划分点[l, r]，如下图

因为下标4 -> 6这部分元素的最终位置已经确定，所以我们只需要判断k是否落在这个区间，如果是则返回nums[k]；如果k < l，说明k在左边部分，则在l的左边部分继续找；如果k > r，说明k在右边部分，则在r的右边部分继续找。

private int bfprt(int[] nums, int begin, int end, int k){
        if(begin == end) return nums[begin];
        int pivot = getMedianOfMedians(nums, begin, end);
        int[] partition = partition(nums, begin, end, pivot);
        if(k >= partition[0] && k <= partition[1]){
            return nums[k];
        }else if(k > partition[1]){
            return bfprt(nums, partition[1] + 1, end, k);
        }else{
            return bfprt(nums, begin, partition[0] - 1, k);
        }
    }

时间复杂度

• 每个组的5个元素排序时间复杂度为O(1)，n / 5组一共就是O(n)
• 取出中位数组成中位数数组O(n)
• 找到中位数数组中的中位数T(n / 5)
• 左右划分后，会折掉一部分数据，最坏情况是T(7n / 10)

medians数组的大小为n / 5，那么medians数组中有n / 10个数比中位数pivot小，而这n / 10个数在自己的组内又有两个数比它小，所以至少有3n / 10个数比pivot小，所以最多有7n / 10个数比pivot大。

最后T(n) = T(7n / 10) + T(n / 5) + O(n)，得到时间复杂度为O(n)

总结

• 随机选择枢轴时，会导致一个不好的情况是partition之后，折掉的数据很少，剩下一部分数据继续递归；bfprt通过修改选择枢轴的策略，保证每次partition后< pivot部分和> pivot部分的元素数量差不多，这样每次就可以折掉很多数据。