Re: [閒聊] 每日LeetCode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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;
: }
: }
: ------------------------------------------------------------
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions,
long long success) {
int i, n = spells.size(), m = potions.size();
vector<int> pairs(n);
vector<double> pot_d(m);
transform(potions.begin(), potions.end(), pot_d.begin(),
[](int i) { return static_cast<double>(i); });
sort(pot_d.begin(), pot_d.end());
for(i = 0; i < n; ++i){
auto pos = lower_bound(pot_d.begin(), pot_d.end(),
(double)success/spells[i]);
pairs[i] = pot_d.end()-pos;
}
return pairs;
}
};
提供用STL的寫法
時間複雜度: O(mlogm+nlogm)=O((m+n)logm)
空間複雜度: O(m)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.47.57 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680459970.A.1D3.html
※ 編輯: yueayase (61.227.47.57 臺灣), 04/03/2023 02:30:10
推
04/03 02:33,
2年前
, 1F
04/03 02:33, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 280 之 719 篇)：