C++でソート済み配列から25%を超えて出現する要素を効率的に見つける方法

問題の概要

配列Aが与えられます。配列には複数の要素が含まれており、その中には重複する要素もあります。この問題では、配列全体の25%を超える割合で出現している要素を1つ見つけて返す必要があります。

例えば、A = [1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7] の場合を考えてみましょう。この配列のサイズは12なので、25%に相当するのは3回です。ここで「4」は4回出現しており、25%を超えているため、答えは「4」となります。

解決のアプローチ

この問題は、ハッシュマップ(unordered_map)を使って各要素の出現回数を数えることで、シンプルに解くことができます。手順は以下の通りです。

• 配列の各要素を順に読み込み、それぞれの出現回数(頻度)をハッシュマップに記録します。
• ある要素の出現回数が配列サイズの25%(n / 4)を超えた時点で、その要素を結果として返します。

実装例(C++)

理解を深めるために、以下のC++での実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
        int findSpecialInteger(vector<int>& arr) {
            int n = arr.size();
            int req = n / 4;
            unordered_map <int, int> m;
            int ans = -1;
            for(int i = 0; i < n; i++){
                m[arr[i]]++;
                if(m[arr[i]] > req)ans = arr[i];
            }
            return ans;
        }
};
main(){
    Solution ob;
    vector<int> c = {1,2,4,4,4,4,5,5,6,6,7,7};
    cout << ob.findSpecialInteger(c);
}

入力

[1,2,4,4,4,4,5,5,6,6,7,7]

出力

4

計算量と補足

上記のハッシュマップを使う方法の時間計算量はO(n)、空間計算量はO(n)となります。実装がシンプルで分かりやすいのが特徴です。

なお、配列がソート済みであることを活かすと、さらに効率的な解法も存在します。25%を超えて出現する要素は、必ず位置 n/4、n/2、3n/4 のいずれかをまたいで連続して現れるため、これら3つの候補位置にある要素について二分探索で出現範囲を調べれば、O(log n)の時間計算量で答えを求めることができます。大規模なデータを扱う場合は、こちらの手法も検討するとよいでしょう。