Pythonで目標値以上の差を持つペアの最大数をカウントするプログラム

問題概要

数値のリスト nums と、もう一つの値 target が与えられているとします。このとき、各ペアが i < j というインデックスの組み合わせであり、i と j が他のどのペアにも重複して使われず、かつ |nums[i] − nums[j]| ≥ target を満たすようなペアの最大数を求める必要があります。

例えば、入力が nums = [2, 4, 6, 10, 11]、target = 5 の場合、出力は 2 になります。これは (2, 10) と (4, 11) という2組のペアを作れるためです。

解法のアプローチ

この問題は「ソート + 二重ポインタ(貪欲法)」で効率的に解けます。リストを昇順にソートすると、前半の要素と後半の要素を組み合わせることで、条件を満たすペアの数が最大化されます。小さい方の要素から順に、target 以上の差を持つ最小の相手を貪欲に探していくのがポイントです。計算量はソートに O(N log N)、ペアの探索に O(N) となります。

具体的には、以下の手順に従います。

• N := リスト A のサイズ
• リスト A をソートする
• ans := 0
• j := N / 2
• i を 0 から N/2 まで繰り返す:
  • j < N かつ A[j] − A[i] < target の間、j := j + 1 を繰り返す
  • j < N であれば、ans := ans + 1 として j := j + 1
• ans を返す

実装例

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

class Solution:
    def solve(self, A, target):
        N = len(A)
        A.sort()
        ans = 0
        j = N >> 1
        for i in range(N >> 1):
            while j < N and A[j] - A[i] < target:
                j += 1
            if j < N:
                ans += 1
                j += 1
        return ans

ob = Solution()
nums = [2, 4, 6, 10, 11]
target = 5
print(ob.solve(nums, target))

入力

[2, 4, 6, 10, 11], 5

出力

2