Pythonで1つの要素を変更して2つの配列を一致させられるか判定する方法

2つの配列 nums1 と nums2、および整数 k が与えられているとします。nums1 のいずれか1つの要素に対して、範囲 [-k, k] 内の任意の値を加えるという操作を一度だけ行うことで、両方の配列を等しくできるかどうかを判定するのがこの問題です。

例えば、入力が nums1 = [5,7,11]、nums2 = [5,5,11]、k = 8 の場合を考えてみましょう。nums1[1](値は7)に -2(範囲 [-8, 8] 内)を加えると 5 になり、nums2 と完全に一致します。したがって、出力は True になります。

解法のアプローチ

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

1. まず、リスト nums1 と nums2 をそれぞれソートします。
2. 不一致箇所が既に見つかったかどうかを示すフラグ temp を False で初期化し、不一致位置を記録する idx を -1 で初期化します。
3. i を 0 から nums1 のサイズ - 1 まで順に処理します。
   • nums1[i] が nums2[i] と異なる場合、すでに temp が True(= 不一致箇所が2つ目以降)であれば False を返します。1回の操作では修正できないためです。
   • そうでなければ temp を True に設定し、idx に i を記録します。
4. ループ終了後、idx が -1(= 最初から両配列が一致している)、または |nums1[idx] - nums2[idx]| <= k(= 差が k 以内で1回の加算で修正可能)であれば True を返します。
5. それ以外の場合は False を返します。

ポイントは「不一致箇所が1つだけ」であることを確認することです。異なる位置が2つ以上あれば、1回の操作で両方を直すことはできません。また、ソートを行うため計算量は O(n log n) となります。

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

実装コード

def solve(nums1, nums2, k):
    nums1.sort()
    nums2.sort()

    temp = False

    idx = -1
    for i in range(len(nums1)):
        if nums1[i] != nums2[i]:
            if temp:
                return False
            temp = True
            idx = i

    if idx == -1 or abs(nums1[idx]-nums2[idx]) <= k:
        return True
    return False

nums1 = [5,7,11]
nums2 = [5,5,11]
k = 8
print(solve(nums1, nums2, k))

入力

[5,7,11], [5,5,11], 8

出力

True