Pythonで数値リストを昇順・降順に並べ替える最小コストを求める方法

問題の概要

数値のリスト nums が与えられたとき、そのリストを昇順または降順のいずれかで並べ替えるために必要な最小コストを求めます。ここでいうコストとは、各要素の元の値と新しい値の差（絶対値）の合計のことです。

例えば、入力が [2, 5, 4] の場合、出力は 2 になります。

解決のアプローチ

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

• 元のリスト nums のコピー temp を作成する
• temp を昇順にソートする
• c1 = 0、c2 = 0 として初期化する
• n にリストのサイズを代入する
• i を 0 から n-1 まで繰り返し処理する：
  • nums[i] が temp[i] と異なる場合、c1 に |nums[i] − temp[i]| を加算する（昇順ソートのコスト）
  • nums[i] が temp[n−1−i] と異なる場合、c2 に |nums[i] − temp[n−i−1]| を加算する（降順ソートのコスト）
• c1 と c2 の小さい方を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution:
    def solve(self, nums):
        temp = nums.copy()
        temp.sort()
        c1 = 0
        c2 = 0
        n = len(nums)
        for i in range(n):
            if nums[i] != temp[i]:
                c1 += abs(nums[i] - temp[i])
            if nums[i] != temp[n-1-i]:
                c2 += abs(nums[i] - temp[n-i-1])
        return min(c1, c2)

ob = Solution()
print(ob.solve([2, 5, 4]))

入力

[2, 5, 4]

出力

2

アルゴリズムの解説

このアルゴリズムでは、まず元のリストを昇順にソートしたコピーを作成します。降順にソートしたリストは、この昇順リストを逆順に並べたものと同じであるため、インデックス n−1−i でアクセスすることで両方向のコストを同時に計算できます。

具体的には、各要素について次の2つの差分を累積します。

• c1：昇順ソート後の同じ位置の要素との差分の合計
• c2：降順ソート後の対応位置の要素との差分の合計

最後に、min(c1, c2) によって、より少ない移動量で済む並べ替え方向を選択します。

計算例：[2, 5, 4] の場合

• 昇順ソート後：[2, 4, 5] → c1 = |2−2| + |5−4| + |4−5| = 0 + 1 + 1 = 2
• 降順ソート後：[5, 4, 2] → c2 = |2−5| + |5−4| + |4−2| = 3 + 1 + 2 = 6

したがって、最小コストは min(2, 6) = 2 となり、これが出力結果と一致します。

この手法の時間計算量は O(n log n)（ソートのコストが支配的）、空間計算量は O(n)（コピー用の配列が必要）であり、効率的に最小コストを求められるのが特徴です。