BFPRT算法学习笔记_综合

BFPRT算法解决的问题？

在O(N)内找到一个数组中找出第k大或第k小的数。

BFPRT算法的思想：

把数组每五个分为一组，分成大概N / 5 组，对每组进行排序。

每组的中位数构成数组medians[] ，用BFPRT找到medians[] 的中位数。不能排序再找它的中位数，因为排序算法复杂

度为O(n*log(n)) ，而medians[] 的数据规模是 N / 5 的。用了那么复杂度就为O(n*log(n))了。

记每组的中位数的中位数为pivot ，用pivot 作为标准进行一次荷兰国旗问题的 patition 过程。把原数组划分为3块。

如果k 在中间那块里面，那么中间那块的数字就为第k小（大）的数。

如果不在，那么看k 是否大于中间那块的终止位置下标，还是小于中间那块的起始位置下标。把原数组切半，再进行BFPRT过程，直到 k 出现在 patition 的中间区域。

可以看到，找中位数的中位数，是为了切patition时，切得更加均匀。另外这样分组后的左右规模就是确定了的，此时估计至少有多少个数比k更大，则确定了左右部分的最大规模。

算法步骤

分组（假设每五个一组，最后剩余的不到五个的一组） O（1）
分组之后每个小组之内排序，跨组不排序，五个数排序，总共需要划分的时间复杂度为O(N)。
将每个组的中位数拿出，构成新的数组，此时新数组长度为N/5（最后不到五个的可以拿上中位数，也可以拿下中位数） O（N）
调用BFPRT算法，此时递归过程中不再寻找k项，而是选择中间的中位数 T（N/5）
下面就是利用上述num，进行荷兰国旗问题排序 O（N）
选择走左边或者走右边

例题：

洛谷1801 黑匣子

题意：给你一个数组memo，要你找m次在memo中从0到 z 这个范围内找第k小的数。

因为z是递增的，所以z前面的数顺序怎样也不影响后面结果。

#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
#include<cstdlib>
#include<bitset>
#include<climits>
#include<functional>
#define F(i,s,t) for(int i=(s);i<=(t);i++)
#define D(i,s,t) for(int i=(s);i>=(t);i--)
#define dBug(i) printf("Value=%d\n",i)
#define ddBug(i,j) printf("Value=%d %d\n",i,j)
#define ed putchar('\n')
#define FO freopen("D:\\in.txt","r",stdin)
#define IOS cin.tie(0) ,cout.tie(0), cout.sync_with_stdio(0)
typedef long long ll;
//const int INF = 1 << 30;
//const double EPS = 1e-6;
//#define MX 102
//#define Mod 10000
using namespace std;class BFPRT{
public://BFPRT算法，在arr数组中从left 到 right 找到第k 小的数int getMinKthByBFPRT(vector<int>& arr, int k, int left, int right){if (arr.empty() || k >= arr.size() || left > right || k < left || k > right){return -1;}//ifif (left == right){return arr.at(left);}//if// 获取每组的中位数组成的数组的中位数(这是BFPTR算法与荷兰国旗问题最大的不同点)// 时间复杂度 O(N)int pivot = medianOfMedians(arr, left, right);//partition过程// 时间复杂度 O(N)vector<int> range = partition(arr, left, right, pivot);//k恰好在 相等的区域内，直接返回if (k > range.at(0) && k < range.at(1)){return arr.at(k);}//if// 根据k所在的范围继续递归if (k <= range.at(0)){return getMinKthByBFPRT(arr, k, left, range.at(0));}//ifelse{return getMinKthByBFPRT(arr, k, range.at(1), right);}//else}private://partition过程 <在左， =在中， >在右，时间复杂度O(N)vector<int> partition(vector<int>& arr, int left, int right, int pivot){int tmpL = left - 1;int tmpR = right + 1;int cur = left;while (cur < tmpR){if (arr.at(cur) < pivot){swap(arr, cur++, ++tmpL);}//ifelse if (arr.at(cur) > pivot){swap(arr, cur, --tmpR);}else{cur++;}}//whilevector<int> res{ tmpL, tmpR };return res;}//获得每组的中位数组成的中位数，时间复杂度O(N)int medianOfMedians(vector<int>& arr, int left, int right){vector<int> medians;int offset = ((right - left + 1) % 5 == 0) ? 0 : 1;int groupNums = (right - left + 1) / 5 + offset;//此过程 (N / 5) * O(1) = O(1)for (int i = 0; i < groupNums; i++){int tmpL = left + i * 5;int tmpR = tmpL + 5;sort(arr.begin() + tmpL, arr.begin() + min(tmpR, right));medians.push_back(arr.at((tmpL + min(tmpR, right) >> 1)));}//forreturn getMinKthByBFPRT(medians, medians.size() / 2, 0, medians.size() - 1);}void swap(vector<int>& arr, int n1, int n2){int tmp = arr.at(n1);arr.at(n1) = arr.at(n2);arr.at(n2) = tmp;}};vector<int> memo, GET;int main()
{int getTime, n;int i, temp;cin >> n >> getTime;for (i = 1; i <= n; i++){cin >> temp;memo.push_back(temp);}for (i = 1; i <= getTime; i++){cin >> temp;GET.push_back(temp);}int popNum = 0;BFPRT s;for (i = 0; i < getTime; i++){cout << s.getMinKthByBFPRT(memo, popNum, 0, GET[i] - 1) << endl;popNum++;}//forreturn 0;
}

结果TLE了。时间复杂度O(n * m)

应该用对顶堆或二叉查找树：

const int MAXN = 500010;
priority_queue<int, vector<int>, greater<int> > smallHeap;
priority_queue<int, vector<int>, less<int> > bigHeap;
int memo[MAXN], GET[MAXN];int main()
{int getTime, n;int i;cin >> n >> getTime;for (i = 1; i <= n; i++){cin >> memo[i];}for (i = 1; i <= getTime; i++){cin >> GET[i];}int p = 0;for (i = 1; i <= getTime; i++){while (p < GET[i]){p++;bigHeap.push(memo[p]);smallHeap.push(bigHeap.top());bigHeap.pop();}//whilebigHeap.push(smallHeap.top());smallHeap.pop();cout << bigHeap.top() << endl;}//forreturn 0;
}