中央値乱択アルゴリズム
O(n)のはず。
結構昔に作ったものだけど、ブログにメモとして載せとく。
確か、アルゴリズムデザインって本を参照したはず。
#include <iostream> #include <vector> #include <ctime> #include <cstdlib> using namespace std; int select(vector<int> S, int k) { int n = S.size(); int i = rand() % n; // n/2; vector<int> R, T; for (int j = 0; j < n; j++) { if (S[j] < S[i]) R.push_back(S[j]); else if (S[j] > S[i]) T.push_back(S[j]); } if (R.size() > k) return select(R, k); else if (n-T.size() <= k) return select(T, k-n+T.size()); else return S[i]; } int main() { srand(time(NULL)); int a[] = {2,1,3,0,4,3,1}; vector<int> S; for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) { S.push_back(a[i]); } for (int i = 0; i < S.size(); i++) { cout << i+1 << "th value : " << select(S, i) << endl; } cout << "median : " << select(S, S.size()/2) << endl; return 0; }
中央値というか、n番目の数値を乱択で求めるアルゴリズムだけど。
ま、でも、アルゴリズム本のクイックソート扱った後の練習問題でよく、「O(n)の中央値選択アルゴリズムを示せ」とか書いてあるから、それの答えってことで。