PythonでO(n)時間・O(1)の追加メモリを使って最大出現回数の数値を見つける方法

問題の概要

サイズ n の配列が与えられ、その要素はすべて 0 から k−1 の範囲に含まれているとします。ここで k は正の整数であり、k ≤ n を満たすものとします。この条件のもとで、配列の中で最も多く出現する数値（最大繰り返し数）を見つけることが課題です。

たとえば、k = 8、A = [3, 4, 4, 6, 4, 5, 2, 8] という入力が与えられた場合、4 は3回出現して最も多いため、出力は 4 となります。

アルゴリズムの考え方

この問題は、ハッシュマップやカウンタ用の追加配列を使わずに解くことができます。ポイントは「各要素の値が必ず k 未満である」という制約を利用することです。インデックス A[i] % k の位置にある値に k を加算していくことで、元の値を壊さずに出現回数の情報を同じ配列内にエンコードできます。

具体的な手順は以下の通りです。

1. n := 配列 A のサイズとする。
2. i を 0 から n−1 まで繰り返す：
   • A[A[i] % k] := A[A[i] % k] + k
3. max_val := A[0]、result := 0 で初期化する。
4. i を 1 から n−1 まで繰り返す：
   • A[i] > max_val であれば、max_val := A[i]、result := i と更新する。
5. result を返す。

処理後の配列では、A[i] を k で割った商が「値 i の出現回数」を表します。したがって、最も大きい値を持つインデックスこそが、最も頻繁に出現する数値ということになります。

実装例

以下にPythonでの実装を示します。

def get_max_repeating(A, k):
    n = len(A)
    # 各値の出現回数を配列自身にエンコードする
    for i in range(n):
        A[A[i] % k] += k
    # 最も加算回数が多いインデックスを求める
    max_val = A[0]
    result = 0
    for i in range(1, n):
        if A[i] > max_val:
            max_val = A[i]
            result = i
    return result

A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

入力

[3, 4, 4, 6, 4, 5, 2, 8], 8

出力

4

計算量について

• 時間計算量： O(n) — 配列を2回走査するだけなので線形時間で完了します。
• 空間計算量： O(1) — カウンタ用の追加配列や辞書を必要とせず、入力配列自体を再利用します。

このように、要素の範囲が 0 以上 k−1 以下という前提があるため、剰余演算によって元の値を復元可能なまま頻度情報を重ね書きできるのがこの手法の妙味です。メモリ使用量を抑えたい競技プログラミングや組み込み開発の場面で特に有効なテクニックと言えるでしょう。