LeetCode:2300. Successful Pairs of Spells and Potions

問題

正の整数配列 spells と potions が与えられます。それぞれ長さ n と m で、spells[i] は i 番目の呪文の強度を、potions[j] は j 番目の薬の強度を表します。

また、整数 success が与えられます。呪文と薬の組み合わせは、その積が success 以上である場合に成功と見なされます。

長さ n の整数配列 pairs を返してください。pairs[i] は、i 番目の呪文と成功する組み合わせを形成するポーションの数を表します。

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:

• 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
• 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
• 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
  Thus, [4,0,3] is returned.

考え方

普通に考えれば spells[i] * potions[j]を２重ループで回して、O(n * m).
しかしこれではタイムオーバー
だから２部探索で考える。
potions.sort()で昇順に並べ直し、left, rightポインタで答えの範囲を更新していく。
２部探索だから計算量は (n+m)log(m).

コード

class Solution(object):
    def successfulPairs(self, spells, potions, success):
        n = len(potions)
        potions.sort()
        res = []

        for i in range(len(spells)):
            l, r = 0, n-1
            while l <= r:
                m = (l+r) // 2
                if potions[m] * spells[i] < success:
                    l = m+1
                else:
                    r = m-1
            res.append(n-l)

        return res