Pythonで相対ソート配列を解く方法：arr2の順序に従った並べ替えの実装例

問題の概要

2つの配列 arr1 と arr2 が与えられます。arr2 の要素はすべて一意（重複なし）であり、arr2 の全要素は arr1 にも含まれています。この条件のもと、arr1 を arr2 と同じ相対的な順序になるように並べ替えます。arr2 に存在しない要素については、arr1 の末尾に昇順で配置します。

例えば、arr1 = [2,3,1,3,2,4,6,7,9,2,19]、arr2 = [2,1,4,3,9,6] の場合、出力は [2,2,2,1,4,3,3,9,6,7,19] になります。

解法のステップ

• 辞書（マップ）D を作成し、arr1 に含まれる各要素の出現回数を記録します。
• 結果を格納する配列 res と、残りの要素を一時的に保持する配列 temp を定義します。
• arr2 の各要素 i に対して、以下を繰り返します。
  • D[i] 回だけ i を res に追加します。
  • D[i] を 0 にリセットします。
• 辞書 D の（キー, 値）ペアを走査し、値が 0 でない場合は、そのキーを値の回数だけ temp に追加します。
• temp をソートし、res の末尾に連結して返します。

Pythonでの実装例

以下のコードは、上記の手順を実際に実装したものです。

class Solution(object):
    def relativeSortArray(self, arr1, arr2):
        d = {}
        for i in arr1:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        res = []
        temp = []
        for i in arr2:
            for j in range(d[i]):
                res.append(i)
            d[i] = 0
        for k, v in d.items():
            if v:
                for i in range(v):
                    temp.append(k)
        temp.sort()
        res.extend(temp)
        return res

ob1 = Solution()
print(ob1.relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]))

入力

[2,3,1,3,2,4,6,7,9,2,19]
[2,1,4,3,9,6]

出力

[2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]

計算量の目安

n を arr1 の長さ、m を arr2 の長さとすると、出現回数の集計に O(n)、arr2 に基づく配置に O(m)、残り要素のソートに O(k log k)（k は arr2 に含まれない要素の総数）がかかります。全体の時間計算量は O(n + m + k log k)、空間計算量は O(n) です。

なお、Pythonでは標準ライブラリの collections.Counter を利用すると、出現回数の集計部分をより簡潔に記述できます。ロジックの本質は変わらないため、まずは上記の基本形を理解しておくと応用が効きやすくなります。