続・PFIサマーインターン2011問題
今更ですが、これの続き。
前回は最悪がO(n2)だったので、最悪をO(n)にしました。
#include <assert.h> #include <algorithm> #include <string> char pfi2011(std::string& s) { assert(!s.empty()); typedef std::string::iterator iter_t; iter_t l = s.begin(), r = s.end(); iter_t const mid = l + s.size()/2; for (unsigned char mask = 1; mask; mask <<= 1) { iter_t const it = std::partition(l, r, [mask](unsigned c) noexcept -> bool { return c & mask; }); if (it < mid) l = it; else r = it; } return *mid; }
書くのは簡単ですね。