推 JIWP: 大師 04/03 01:37
→ Firstshadow: 大師 04/03 01:38
推 Che31128: 大師 04/03 01:39
推 pomelotea: 開始binary search week了 04/03 01:54
→ pandix: 大師 04/03 02:33
2300. Successful Pairs of Spells and Potions
給定兩個陣列spells和points，前者表示多個咒語的強度，後者表示多個藥劑的強度，若
咒語和藥劑相乘大於success則這一組咒語和藥劑配對成功，返回一個長度為spells的陣列
pairs，其中 pairs[i] 是能與第 i 個咒語配對成功的藥劑數量。
Example：
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.
思路：
1.最簡單的方法就是兩個陣列相互配對並計算數量，但是咒語和藥劑的長度很大這樣做
肯定會吃TLE。
2.我們可以先把藥劑的強度排序好，每個咒語使用二分搜索找到最小且滿足success的
藥劑，這樣這個索引的右邊全部都是配對成功的藥劑，若potions.length = n
滿足數量就會是 n - index，如果最右邊(最大)的藥劑和咒語不滿足則二分搜索直接
返回n不用繼續找尋。
Java Code：
------------------------------------------------------------
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
long[] arr = new long[potions.length];
Arrays.sort(potions);
for (int i = 0; i < potions.length; i++) {
arr[i] = potions[i];
}
int[] ans = new int[spells.length];
for (int i = 0; i < spells.length;i++) {
int index = search(arr, spells[i], success);
ans[i] = potions.length - index;
}
return ans;
}
private int search(long[] arr, long spell, long target) {
int n = arr.length;
if (arr[n - 1] * spell < target) {
return n;
}
int l = 0;
int r = n - 1;
while (l < r) {
int mid = (l + r)/2;
if (arr[mid] * spell >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
}
------------------------------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680457044.A.E5B.html