Pythonで2つのリストの要素間の最小差を求めるプログラム

2つのリスト間の最小差とは

2つのリスト L1 と L2 が与えられたとき、L1 のある要素と L2 のある要素を組み合わせたときに生じる「差」の中で、最も小さいもの（絶対値が最小となる差）を求める問題です。

例えば、入力が L1 = [2, 7, 4]、L2 = [16, 10, 11] の場合、出力は 3 になります。これは、10 − 7 = 3 という差が最も小さいためです。

解法のアプローチ：ソート＋双方向ポインタ

この問題は、両方のリストをソートしてから、2つのポインタを使って効率的に比較していくことで解けます。手順は以下の通りです。

• リスト L1 をソートし、リスト L2 もソートする
• ans := 無限大（初期値）
• i := 0、j := 0 とする
• i が L1 のサイズ未満、かつ j が L2 のサイズ未満である間、以下を繰り返す
  • ans := ans と |L1[i] − L2[j]| の小さい方を代入
  • L1[i] < L2[j] の場合は i := i + 1
  • そうでなければ j := j + 1
• ans を返す

このアルゴリズムでは、小さい方の要素のポインタを進めることで、常に「今考えうる最小差」を見逃さずにチェックできます。計算量はソートに O(n log n)、比較部分は O(n + m) となり、全組み合わせを総当たりする O(n × m) よりも大幅に高速です。

実装例

以下はPythonでの実装例です。

class Solution:
    def solve(self, L1, L2):
        L1.sort()
        L2.sort()
        ans = float("inf")
        i = j = 0
        while i < len(L1) and j < len(L2):
            ans = min(ans, abs(L1[i] - L2[j]))
            if L1[i] < L2[j]:
                i += 1
            else:
                j += 1
        return ans

ob = Solution()
L1 = [2, 7, 4]
L2 = [16, 10, 11]
print(ob.solve(L1, L2))

入力

[2, 7, 4], [16, 10, 11]

出力

3

コードのポイント

この実装における重要なポイントは次のとおりです。

• float("inf")：無限大を初期値として使うことで、最初の比較で必ず実際の差に置き換わります。
• abs() 関数：差の絶対値を取ることで、どちらのリストの要素が大きい場合でも正しく最小差を求められます。
• ポインタの進め方：より小さい側のポインタを進めることで、差が縮まる可能性のあるペアだけを効率的に調べます。