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(</int></cstdlib></ctime></vector></iostream>…