2300. Successful Pairs of Spells and Potions

Medium

題目描述

Description

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

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.

Example 2:

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

• 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
• 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
• 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
  Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

解答

Solution

/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function (spells, potions, success) {
  const result = [];
  const sortPotions = potions.sort((a, b) => a - b);

  for (let i = 0; i < spells.length; i++) {
    let left = 0;
    let right = sortPotions.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (spells[i] * sortPotions[mid] < success) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    result.push(sortPotions.length - left);
  }

  return result;
};

解題思路

需要根據 spells 陣列中的每個元素來找到符合條件的 potions 陣列中的元素，再計算出符合條件的元素的數量，並將數量 push 到 result 陣列中。

使用 binary search 來解題，因為 potions 陣列不一定是照順序，所以要先對 potions 陣列進行排序

const sortPotions = potions.sort((a, b) => a - b);
// sort((a, b) => a - b) 代表由小到大排序，[3,1,2,4] => [1,2,3,4]

再來遍歷 spells 陣列，透過 binary search 來找到符合條件的 potion 的起點。
根據起點來計算出符合條件的 potion 的數量，並將數量 push 到 result 陣列中。

for (let i = 0; i < spells.length; i++) {
  let left = 0;
  let right = sortPotions.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (spells[i] * sortPotions[mid] < success) {
      left = mid + 1;
      /* 如果小於 success 代表符合條件的 potion 的起點在右邊，
         故要把目前的 mid 當成新的 left，繼續往右邊找 */
    } else {
      right = mid - 1;
      /* 反之則把目前的 mid - 1 當成新的 right，繼續往左邊找。
           如果不減一則有可能讓 mid 還是同一個值，導致無限迴圈 */
    }
  }

  result.push(sortPotions.length - left);
}

心得

不太直觀，若不使用 binary search 的話會導致 Time Limit Exceeded，故需要使用時間複雜度為 O(log n) 的 binary search。