IDEA激活码BFPTR算法-求TOP-K问题
求TOP-K问题最简单的方式为快速排序后取前K大的即可。但是这样做有两个问题
-
快速排序的平均复杂度为 O(NlogN) ，但最坏时间复杂度为 O(N^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提出。该算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。
一. 快速排序原理
先来看看快速排序是如何进行的，一趟快速排序的过程如下
- 先从序列中选取一个数作为基准数
- 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边(荷兰国旗问题)
一趟快速排序也叫做Partion，即将序列划分为两部分，一部分比基准数小，另一部分比基准数大，然后再进行分治过程，每一次Partion不一定都能保证划分得很均匀，所以最坏情况下的时间复杂度不能保证总是为 O(NlogN).。对于Partion过程，通常有两种方法
1. 两个指针从首尾向中间扫描（双向扫描）
这种方法可以用挖坑填数来形容，比如
初始化：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才停止，最终得到结果如下
上述过程就是一趟快速排序。
二. BFPRT算法原理
在BFPTR算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。算法步骤如下
// 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);
}
}
// 利用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分区操作
本文参考了：
- BFPRT算法原理
