Pythonで最も頻出する上位K個の要素を求めるアルゴリズムを解説

問題概要

空ではない整数型の配列が与えられたとき、その中で最も頻繁に出現する上位k個の要素を返すことを考えます。

例えば、要素が [1,1,1,1,2,2,3,3,3] で k = 2 の場合、結果は [1, 3] となります。

解法のアプローチ

この問題は、ハッシュマップ（辞書）を2つ使うことで効率的に解くことができます。全体の流れは以下の通りです。

1. 出現回数の記録： 各数値の出現回数を最初のマップに記録します。
2. 頻度ごとのグループ化： 「出現回数」をキー、「その回数で出現した数値のリスト」を値とする2つ目のマップを作成します。
3. 頻度の高い順に抽出： 配列の長さから降順にループし、該当する頻度の要素を結果リストへ追加していきます。
4. 早期終了： 結果リストの長さがk以上になった時点でループを抜けます。

具体的な手順

• num_freq（空のマップ）と freq_list（空のマップ）を用意します。
• nums の各要素 i について、i が num_freq に存在しなければ num_freq[i] := 1 とし、存在すれば num_freq[i] を1増やします。
• num_freq の各キー・バリューのペアについて、value が freq_list に存在しなければ freq_list[value] := [key] とし、存在すれば freq_list[value] のリストに key を挿入します。
• res := 空のリストとします。
• i を配列の長さから 0 まで減らしながらループし、i が freq_list に存在すれば freq_list[i] の要素を res に追加します。
• res の長さが k 以上になったら break します。
• 結果を返します。

Pythonでの実装例

それでは、理解を深めるために実際のコードを見てみましょう。

class Solution(object):
    def topKFrequent(self, nums, k):
        number_frequency = {}
        frequency_list = {}
        for i in nums:
            if i not in number_frequency:
                number_frequency[i] = 1
            else:
                number_frequency[i] += 1
        for key, value in number_frequency.items():
            if value not in frequency_list:
                frequency_list[value] = [key]
            else:
                frequency_list[value].append(key)
        result = []
        for i in range(len(nums), 0, -1):
            if i in frequency_list:
                result.extend(frequency_list[i])
            if len(result) >= k:
                break
        return result

ob1 = Solution()
print(ob1.topKFrequent([1,1,1,1,2,2,3,3,3], 2))

入力

[1,1,1,1,2,2,3,3,3]
2

出力

[1, 3]

計算量について

このアルゴリズムの時間計算量は O(n) です（n は配列の長さ）。出現回数のカウントに O(n)、頻度ごとのグループ化にも O(n)、最後のループは最大でも O(n) で完了します。空間計算量も同様に O(n) となります。ソートベースの手法（O(n log n)）と比べて高速に動作する点が大きな特徴です。