LeetCode Weekly Contest 149: Online Majority Element In Subarray

問題概要

はじめに、長さ の数列 が与えられるので、以下のクエリにオンラインで答えよ。

• の 番目から 番目の間に 回以上出現するものを答えよ。なお は区間の長さの半分を真に超えるため該当する場合は 1 つしか該当しない。そのような要素がなければ -1 と答えよ。

解説

クエリの長さで平方分割を行う。ある があって、クエリで与えられる区間の長さが 以下であるかどうかで場合分けを行う。

• 長さが 以下である場合
  • この場合は から までを愚直に調べて、最も多いものが条件を満たすかどうかを見ればよい。
• 長さが 以上である場合
  • クエリで与えられる区間の長さを とする。クエリの条件より、答えが存在するならばその数は区間内に 回を超えて出現するはずであるため、そもそも数列内に 回以下しか登場しない要素について調べる必要がない。そして、 であることから、調べるべき要素の種類数は高々 個である。よって、各要素についてインデックス列を持ち二分探索を行うことで処理できる。

と置くと、前者の処理で に、後者の処理で となるので、高速に処理可能である。

別解

知りたいのは区間内の majority なので、区間内にある値を乱択し、それが majority であるかどうかをチェックするだけでも高い確率で通る。majority ならば選ばれる確率はだいたい 2 分の 1 で、20 回試行したときにそれを全部外すのは なので、確率としてはとても低い。

ソースコード

愚直に調べるパートには Boyer-Moore majority vote algorithm を使用している。線形だけど定数倍が軽そう。

class MajorityChecker {
public:
    vector<int> vec;
    unordered_map< int, vector<int> > rec;
    vector< pair<int, int> > occur;
    int s;
    MajorityChecker(vector<int>& arr) {
        this->vec = arr;
        int N = vec.size(); s = sqrt(N);
        for(int i=0; i<N; i++) {
            rec[ vec[i] ].emplace_back(i);
        }
        for(auto e : rec) {
            occur.emplace_back(e.second.size(), e.first);
        }
        sort(occur.rbegin(), occur.rend());
    }
    
    int query(int left, int right, int threshold) {
        right++;
        if(right - left <= s) {
            int cand = 0, cnt = 0;
            for(int i=left; i<right; i++) {
                if(cnt == 0) cand = vec[i], cnt = 1;
                else if(cand == vec[i]) cnt++;
                else cnt--;
            }
            for(int i=left; i<right; i++) {
                if(vec[i] == cand) threshold--;
            }
            return (threshold <= 0 ? cand : -1);
        }
        else {
            for(size_t k=0; k<occur.size(); k++) {
                int cand = occur[k].second, cnt = occur[k].first;
                if(cnt < threshold) break;
                auto u = lower_bound(rec[cand].begin(), rec[cand].end(), right);
                auto d = lower_bound(rec[cand].begin(), rec[cand].end(), left );
                if(u - d >= threshold) return cand;
            }
            return -1;
        }
    }
};

これは勉強になりました。