找到n个元素中的最大/小值，比较次数为n-1, 找到n个元素中的最大值和最小值，可以Two Pass，比较次数为2n-2 也可以One Pass，比较次数至多为\(\left \lfloor 3n/2 \right \rfloor\) 首先对最大值和最小值进行初始化，n为奇数时MAX和MIN均初始化v[0]，n为偶数时MAX和MIN分别初始化为v[0]和v[1]中的最大值和最小值 然后每两个数比较一次，小的数和MIN比较，大的数和MAX比较，共进行三次
对于n为奇数，总比较次数为\(3(n-1)/2 = \left \lfloor 3n/2 \right \rfloor\)对于n为偶数，总比较次数为\(3(n-2)/2 + 1= 3n/2 - 2\)无论哪种情况，总的比较次数至多为\(\left \lfloor 3n/2 \right \rfloor\)
#include <iostream> #include <vector> using namespace std; void findMaxMin(vector<int>& v){ int n = v.size(); if(n == 0) return; int MIN, MAX, i; if(n % 2 == 0){ if(v[0] > v[1]) { MIN = v[1]; MAX = v[0]; } else { MIN = v[1]; MAX = v[0]; } i = 2; } else { i = 1; MIN = MAX = v[0]; } while(i < n){ if(v[i] < v[i+1]){ MIN = min(v[i], MIN); MAX = max(v[i+1], MAX); } else { MIN = min(v[i+1], MIN); MAX = max(v[i], MAX); } i += 2; } cout << "MAX = " << MAX << ", MIN = " << MIN << endl; } int main(){ vector<int> v{1,4,3,2,5,6,0,9,6,8,8,9}; findMaxMin(v); return 0; }BFPRT算法可以在O(n)最坏时间复杂度找到第k大，也可用于解决TOP-K问题215. Kth Largest Element in an Array 随机化使用均摊的思想就不写了，用BFPRT检验下 严格的BFPRT
class Solution { public: void InsertSort(vector<int>& a, int l, int r){ for(int i = l + 1; i <= r; i++){ auto x = a[i]; auto j = i; while(j > l && x < a[j-1]){ a[j] = a[j-1]; j--; } a[j] = x; } } int Partiton(vector<int>& a, int l, int r, int m){ int x = a[m]; int i = l; int j = r; swap(a[m], a[l]); while(i < j){ while(i < j && a[j] >= x) j--; a[i] = a[j]; while(i < j && a[i] <= x) i++; a[j] = a[i]; } a[i] = x; return i; } int BFPRT(vector<int>& a, int l, int r, int k){ if(r - l + 1 < 5) { InsertSort(a, l, r); return l + k - 1; } int e = l - 1; for(int i = l; i + 4 <= r; i += 5){ InsertSort(a, i, i+4); swap(a[++e], a[i+2]); } int m = BFPRT(a, l, e, (e - l + 1) / 2 + 1); int p = Partiton(a, l, r, m); int n = p - l + 1; if(n == k) return p; if(n > k) return BFPRT(a, l, p-1, k); return BFPRT(a, p+1, r, k - n); } int findKthLargest(vector<int>& nums, int k) { return nums[BFPRT(nums, 0, nums.size()-1, nums.size() - k + 1)]; } };我自己最开始的写法，对找中位数的BFPRT函数做了特殊处理，使用FindMin代替，减少了无必要的BFPRT递归调用
class Solution { public: int InsertSort(vector<int>& a, int l, int r){ for(int i = l + 1; i <= r; i++){ auto x = a[i]; auto j = i; while(j > l && x < a[j-1]){ a[j] = a[j-1]; j--; } a[j] = x; } return l + (r - l) / 2; } int Partiton(vector<int>& a, int l, int r, int m){ int x = a[m]; int i = l; int j = r; swap(a[m], a[l]); while(i < j){ while(i < j && a[j] >= x) j--; a[i] = a[j]; while(i < j && a[i] <= x) i++; a[j] = a[i]; } a[i] = x; return i; } int FindMid(vector<int>& a, int l, int r){ if(r - l + 1 < 5) return InsertSort(a, l, r); int p = l - 1; for(int i = l; i < r - 5; i += 5){ int mid = InsertSort(a, i, i+4); swap(a[++p], a[mid]); } return FindMid(a, l, p); } int BFPRT(vector<int>& a, int l, int r, int k){ if(l == r) return a[l]; int m = FindMid(a, l, r); int p = Partiton(a, l, r, m); int n = p - l + 1; if(n == k) return a[p]; if(n > k) return BFPRT(a, l, p, k); return BFPRT(a, p+1, r, k - n); } int findKthLargest(vector<int>& nums, int k) { return BFPRT(nums, 0, nums.size()-1, nums.size() - k + 1); } };当找到中位数的中位数时，除了不能被n整除的剩余组和包含有x的那个组除外，至少有一半的组中每个组至少3个元素大于x，所以大于x的元素个数最少为\[ \begin{aligned} 3 \left \lceil \frac{1}{2}\left \lceil \frac{n}{5}\right \rceil{} -2 \right \rceil \geq \frac{3n}{10} - 6 \end{aligned} \] 递归选第k大最多有\(7n/ 10 + 6\)个元素 最坏情况下\(T(n) \leq T(\left \lceil n/5 \right \rceil) + T(7n/ 10 + 6) + O(n)\) 假定\(T(n) \leq cn\) 且\(O(n)\)的上界为\(an\)\[ \begin{aligned} T(n) &\leq c\left \lceil n/ 5 \right \rceil + c(7n/ 10 + 6) + an\\ &\leq cn/5 + c + 7cn/10 + 6c + an \\ & = 9cn / 10 + 7c + an \\ & = cn + (-cn/10) + 7c + an \end{aligned} \]
只要使得\(-cn/10 + 7c + an \leq 0\)即可， 也就是$c \geq 10a(n / n - 70) $ 假设n>140,则\((n / n - 70) \leq 2\), 选择\(c \geq 20a\)即可
k分位数
转载于:https://www.cnblogs.com/qbits/p/11171619.html
