今天在用 C++ 重複練習 2197. Replace Non-Coprime Numbers in Array 一遍,試著寫出跑得更快的版本,發現自己寫出來的 gcd 在 LeetCode 平台上反而跑得比較快,目前還不曉得背後到底是怎麼一回事,先記錄一下,目前想到的做法是盡量避免呼叫 gcd 以及盡量使用已使用的記憶體空間來加速,最好的時候可以跑到 Runtime 2ms Beats 98.62% 的成績。
class Solution {
int gcd(int a, int b) {
if (b > a)
swap(a, b);
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}
public:
vector<int> replaceNonCoprimes(vector<int>& nums) {
int idx = 0;
for (int i = 1; i < nums.size(); ++i) {
int num = gcd(nums[idx], nums[i]);
if (num == 1)
nums[++idx] = nums[i];
else
nums[idx] = nums[idx] / num * nums[i];
for (int j = idx; j > 0; --j) {
int num = gcd(nums[j], nums[j - 1]);
if (num == 1)
break;
nums[j - 1] *= nums[j] / num;
--idx;
}
}
nums.resize(idx + 1);
return nums;
}
};
沒有留言:
張貼留言