Pythonでソート済み配列の各要素と他の要素との絶対差の合計を効率的に求めるプログラム

問題の概要

非減少順(昇順)にソートされた整数配列 nums が与えられます。ここで、nums と同じ長さを持つ配列 result を作成し、result[i] には nums[i] と配列内の他のすべての要素との絶対差の合計を格納することを考えます。

たとえば、入力が nums = [5, 7, 12] の場合、出力は [9, 7, 12] となります。これは次のように計算されます。

• |5−5| + |5−7| + |5−12| = 0 + 2 + 7 = 9
• |7−5| + |7−7| + |7−12| = 2 + 0 + 5 = 7
• |12−5| + |12−7| + |12−12| = 7 + 5 + 0 = 12

解法のアプローチ

素朴な方法では、各要素ごとに他のすべての要素との差を計算するため、時間計算量は O(n²) になってしまいます。しかし、配列がすでにソートされているという性質を利用すると、隣接する要素間の差分だけを使って結果を順次更新でき、時間計算量 O(n) の効率的なアルゴリズムを実現できます。

具体的な手順は以下の通りです。

• res := 新しい空のリスト
• s := 0
• n := nums の要素数
• i を 1 から n−1 までループ:
  • s := s + nums[i] − nums[0]
  (この時点の s が result[0] の値になります)
• s を res の末尾に追加
• i を 1 から n−1 までループ:
  • diff := nums[i] − nums[i−1]
  • s := s + diff × i(現在位置より前の i 個の要素は diff だけ遠ざかる)
  • s := s − diff × (n − i)(現在位置以降の n−i 個の要素は diff だけ近づく)
• s を res の末尾に追加
• res を返す

この更新式により、直前の要素に対する答えから次の要素に対する答えを O(1) で導き出せるのがポイントです。これにより、全体の計算量を大幅に削減できます。

実装例

以下の Python コードで実際の動作を確認できます。

def solve(nums):
    res = []
    s = 0
    n = len(nums)
    for i in range(1, n):
        s += nums[i] - nums[0]
    res.append(s)
    for i in range(1, n):
        diff = nums[i] - nums[i-1]
        s += diff * i
        s -= diff * (n - i)
        res.append(s)
    return res

nums = [5, 7, 12]
print(solve(nums))

入力

[5, 7, 12]

出力

[9, 7, 12]