Pythonで最大頻度と同じ出現回数を持つ最短サブリストの長さを求める方法

数値のリスト nums が与えられたとします。nums 内で最も頻度が高い数値の出現回数を k とするとき、「その中で最も頻度の高い要素の出現回数も同じく k となるような、最短の部分リスト」の長さを求めるのが今回の課題です。

問題の例

例えば、入力が nums = [10, 20, 30, 40, 30, 10] の場合、出力は 3 になります。

このリストでは 10 と 30 がそれぞれ 2 回出現しており、最大頻度は k = 2 です。ここで部分リスト [30, 40, 30] を選ぶと、30 を含み、かつ 30 の出現回数も 2 回である最短の部分リストとなります。そのため答えは長さ 3 です。

解決のアプローチ

この問題は、次の手順で解くことができます。

• L: nums の要素数を取得します。
• rnums: nums を逆順に並べ替えたリストを作成します。
• d: nums 内の各要素の出現回数を格納したマップ（Counter）を作成します。
• mx: d のすべての値の中から最大値（最大頻度）を求めます。
• vs: 出現回数が mx と一致する要素（キー）のリストを抽出します。
• mn: 初期値として L を設定します。
• vs の各要素 v について、mn = min(mn, L - rnums.index(v) - nums.index(v)) を計算します。これは「先頭側で最初に現れる位置」と「末尾側で最初に現れる位置」の間隔から、その要素を含む最小範囲の長さを求める計算です。
• 最終的な mn を返します。

Pythonによる実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

from collections import Counter

def solve(nums):
    L = len(nums)
    rnums = nums[::-1]

    d = Counter(nums)
    mx = max(d.values())
    vs = [k for k in d if d[k] == mx]

    mn = L
    for v in vs:
        mn = min(mn, (L - rnums.index(v)) - nums.index(v))
    return mn

nums = [10, 20, 30, 40, 30, 10]
print(solve(nums))

入力

[10, 20, 30, 40, 30, 10]

出力

3

アルゴリズムのポイント

この解法の鍵は、逆順リスト rnums を活用する点にあります。ある要素 v について、nums.index(v) は先頭から見た最初の出現位置、rnums.index(v) は末尾から見た最初の出現位置を表します。両者を組み合わせることで、v の全出現回数を含む最小の連続範囲の長さを効率的に算出できます。

計算量は、Counter の構築と各要素の index 検索により、要素数を n として O(n²) 程度になります。より大規模なデータに対しては、各要素の出現位置を事前に記録しておくことで O(n) まで改善することも可能です。