2025年9月17日 星期三

C++ 自製的 gcd 比標準函式庫提供的跑得還要快?

今天在用 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;
    }
};

沒有留言: