BFPTR算法-求TOP-K问题

求TOP-K问题最简单的方式为快速排序后取前K大的即可。但是这样做有两个问题

1. 快速排序的平均复杂度为 O(NlogN) ，但最坏时间复杂度为 O(N^2)

2. 我们只需要前 K大的，而对其余不需要的数也进行了排序，浪费了大量排序时间。

而堆排序也是一个较好的方法，维护一个大小为 K 的堆，时间复杂度为 O(NlogN).

public static class MaxHeapComparator implements Comparator<Integer> {

   @Override
   public int compare(Integer o1, Integer o2) {
      return o2 - o1;
   }
}

// 利用大根堆，时间复杂度O(N*logK)
public static int minKth1(int[] arr, int k) {
   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapComparator());
   for (int i = 0; i < k; i++) {
      maxHeap.add(arr[i]);
   }
   for (int i = k; i < arr.length; i++) {
      if (arr[i] < maxHeap.peek()) {
         maxHeap.poll();
         maxHeap.add(arr[i]);
      }
   }
   return maxHeap.peek();
}

这里介绍一个比较好的算法，叫做BFPTR算法，又称为中位数的中位数算法，它的最坏时间复杂度为 O(n) ，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。

一. 快速排序原理

先来看看快速排序是如何进行的，一趟快速排序的过程如下

1. 先从序列中选取一个数作为基准数
2. 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边(荷兰国旗问题)

一趟快速排序也叫做Partion，即将序列划分为两部分，一部分比基准数小，另一部分比基准数大，然后再进行分治过程，每一次Partion不一定都能保证划分得很均匀，所以最坏情况下的时间复杂度不能保证总是为 O(NlogN).。对于Partion过程，通常有两种方法

1. 两个指针从首尾向中间扫描（双向扫描）

这种方法可以用挖坑填数来形容，比如

img

初始化：i = 0; j = 9; pivot = a[0];

现在a[0]保存到了变量pivot中了，相当于在数组a[0]处挖了个坑，那么可以将其它的数填到这里来。从j开始向前找一个小于或者等于pivot的数，即将a[8]填入a[0]，但a[8]又形成了一个新坑，再从i开始向后找一个大于pivot的数，即a[3]填入a[8]，那么a[3]又形成了一个新坑......

就这样，直到i==j才停止，最终得到结果如下

img

上述过程就是一趟快速排序。

二. BFPRT算法原理

在BFPTR算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。算法步骤如下

算法步骤 image-20210525163141281

// arr[L..R]  如果排序的话，位于index位置的数，是什么，返回
public static int bfprt(int[] arr, int L, int R, int index) {
   if (L == R) {
      return arr[L];
   }
   int pivot = medianOfMedians(arr, L, R);//最终剩下的数字即为pivot（精挑细选一个数pivot）
   int[] range = partition(arr, L, R, pivot);
   if (index >= range[0] && index <= range[1]) {//判断pivot的位置与k的大小，有选择的对左边或右边递归。
      return arr[index];
   } else if (index < range[0]) {
      return bfprt(arr, L, range[0] - 1, index);
   } else {
      return bfprt(arr, range[1] + 1, R, index);
   }
}

image-20210525173549023 image-20210525173619842

// 利用bfprt算法，时间复杂度O(N)
public static int minKth3(int[] array, int k) {
   int[] arr = copyArray(array);
   return bfprt(arr, 0, arr.length - 1, k - 1);
}

// arr[L..R]  如果排序的话，位于index位置的数，是什么，返回
public static int bfprt(int[] arr, int L, int R, int index) {
   if (L == R) {
      return arr[L];
   }
   int pivot = medianOfMedians(arr, L, R);
   int[] range = partition(arr, L, R, pivot);
   if (index >= range[0] && index <= range[1]) {
      return arr[index];
   } else if (index < range[0]) {
      return bfprt(arr, L, range[0] - 1, index);
   } else {
      return bfprt(arr, range[1] + 1, R, index);
   }
}

// arr[L...R]  五个数一组
// 每个小组内部排序
// 每个小组中位数领出来，组成marr
// marr中的中位数，返回
public static int medianOfMedians(int[] arr, int L, int R) {
   int size = R - L + 1;
   int offset = size % 5 == 0 ? 0 : 1;
   int[] mArr = new int[size / 5 + offset];
   for (int team = 0; team < mArr.length; team++) {
      int teamFirst = L + team * 5;
      // L ... L + 4
      // L +5 ... L +9
      // L +10....L+14
      mArr[team] = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));//每个组的中位数组成的数组
   }
   // marr中，找到中位数
   // marr(0, marr.len - 1,  mArr.length / 2 )
   return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);//中位数的数组，递归bfprt
}

public static int getMedian(int[] arr, int L, int R) {
   insertionSort(arr, L, R);
   return arr[(L + R) / 2];
}

public static void insertionSort(int[] arr, int L, int R) {//插入排序
   for (int i = L + 1; i <= R; i++) {
      for (int j = i - 1; j >= L && arr[j] > arr[j + 1]; j--) {
         swap(arr, j, j + 1);
      }
   }
}
public static void swap(int[] arr, int i1, int i2) {
        int tmp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = tmp;
}

• 调试过程

[55, 52, 41, 61, 99, 85, 33, 22, 14, 85, 79, 34, 98, 0, 33, 21, 22, 13, 69, 66, 55, 57, 78, 95, 82, 55, 100, 2, 28, 84, 19, 83, 99, 67, 73, 15, 60, 97, 94, 20]

[55, 33, 34, 22, 78, 55, 73, 60]

[34, 60]

[34]

最终剩下的数字即为pivot，然后进行partition分区操作

image-20210525180544979

本文参考了：

• BFPRT算法原理