Pythonで要素の出現頻度が少ない順に配列をソートするプログラム

問題の概要

同じ要素が複数回出現する可能性のある配列が与えられたとします。この配列を、出現頻度が少ない順（頻度の昇順）に並べ替えることを考えます。つまり、出現回数が最も少ない要素から先に並べ、以降も頻度の昇順に従ってソートしていきます。

例えば、入力が nums = [1,5,3,1,3,1,2,5] の場合、出力は [2, 5, 5, 3, 3, 1, 1, 1] となります。

この例では、「2」は1回、「5」と「3」はそれぞれ2回、「1」は3回出現します。そのため、頻度の少ない順に「2 → 5 → 3 → 1」の順で並びます。なお、同じ頻度の要素同士（5と3）は、値の大きい方から先に並ぶ点にも注目してください。

解決の手順

• 新しいマップ（辞書）mp を用意する
• nums 内の各一意な要素 i について以下を実行する：
  • x := nums における i の出現回数
  • x が mp に既に存在する場合は、mp[x] の末尾に i を追加する
  • 存在しない場合は、mp[x] := 要素 i のみを含むリストとする
• 結果格納用の新しいリスト ans を用意する
• キーでソートした mp の各 i について：
  • mp[i] を降順にソートした各 j について、j を i 回 ans に挿入する
• ans を返す

Pythonでの実装例

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

def solve(nums):
    mp = {}
    for i in set(nums):
        x = nums.count(i)
        try:
            mp[x].append(i)
        except:
            mp[x] = [i]
    ans = []

    for i in sorted(mp):
        for j in sorted(mp[i], reverse=True):
            ans.extend([j] * i)
    return ans

nums = [1,5,3,1,3,1,2,5]
print(solve(nums))

入力

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

出力

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

コードのポイント

set(nums) で重複を除去した各要素に対して count() で出現回数を調べ、頻度をキーとした辞書を作成しています。その後、頻度（キー）を昇順にソートし、同じ頻度を持つ要素は reverse=True によって降順に並べて出力しています。

なお、nums.count(i) はリスト全体を走査するため、要素ごとに O(n) の計算量がかかります。パフォーマンスを向上させたい場合は、標準ライブラリの Collections.Counter を使うと、一度の走査で全要素の出現回数を効率的に取得できます。