Pythonで最小の絶対差合計を求めるプログラム

同じサイズを持つ2つの正数配列 nums1 と nums2 があるとします。これらの配列の絶対差合計（absolute sum difference）とは、各インデックス i（0 ≤ i < n）における |nums1[i] − nums2[i]| の総和のことです。

ここで、絶対差合計を最小化するために、nums1 の要素を最大1つだけ、nums1 内に存在する別の任意の要素で置き換えることができるものとします。このとき、要素を最大1つ置き換えた後の最小絶対差合計を求めてください。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

問題の例

たとえば、入力が nums1 = [2,8,6]、nums2 = [3,4,6] の場合、出力は 3 になります。最適な解は次の2通りが考えられます。

• インデックス1の要素をインデックス0の要素で置き換える：[2,8,6] → [2,2,6]
• インデックス1の要素をインデックス2の要素で置き換える：[2,8,6] → [2,6,6]

どちらの場合も、差の合計は |2−3| + （|2−4| または |6−4|） + |6−6| = 3 となります。

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

1. nums1 と nums2 が完全に一致している場合は 0 を返します。
2. 変数 minn_diff を負の無限大、ind を −1 で初期化します。
3. i を 0 から len(nums1) - 1 まで繰り返し、差が最大となるインデックス ind を見つけます。この位置が置き換え対象の候補です。
4. diff := |nums1[ind] − nums2[ind]| とし、index := ind とします。
5. 再びすべての i について、i ≠ ind のときに |nums1[i] − nums2[ind]| < diff を満たす要素を探します。これにより、ind の位置の nums2[ind] に最も近い値を持つ置き換え元の要素 index が求まります。
6. 合計値 summ を計算します。i == ind の場合は |nums1[index] − nums2[i]| を加算し、それ以外の場合は元の |nums1[i] − nums2[i]| を加算します。
7. 最後に summ mod (10^9 + 7) を返します。

実装コード

理解を深めるために、実際のPythonでの実装を見てみましょう。

def solve(nums1, nums2):
    if(nums1==nums2):
        return(0)

    minn_diff = float('-inf')
    ind = -1
    for i in range(len(nums1)):
        if(abs(nums1[i]-nums2[i]) > minn_diff):
            ind = i
            minn_diff = abs(nums1[i]-nums2[i])

    diff = abs(nums1[ind]-nums2[ind])
    index = ind
    for i in range(len(nums1)):
        if(i!=ind):
            if(abs(nums1[i]-nums2[ind])<diff):
                index = i
                diff = abs(nums1[i]-nums2[ind])

    summ = 0
    for i in range(len(nums1)):
        if(i==ind):
            summ += abs(nums1[index]-nums2[i])
        else:
            summ += abs(nums1[i]-nums2[i])
    return(summ%(10**9 + 7))

nums1 = [2,8,6]
nums2 = [3,4,6]
print(solve(nums1, nums2))

入力

[2,8,6], [3,4,6]

出力

3

計算量について

この実装では、配列全体をスキャンして最大差の位置を特定する処理と、置き換え候補を探す処理にそれぞれ O(n)、最終的な合計計算にも O(n) の時間がかかるため、全体の時間計算量は O(n)、空間計算量は O(1) となります。なお、より厳密には置き換え候補の探索を二分探索（bisect モジュール）を用いて最適化することで、O(n log n) の計算量で全パターンを網羅的に評価することも可能です。