2197. Replace Non-Coprime Numbers in Array

Leetcode link

题目简介

这是一道 hard，题目会给一个数字组成的数组 nums 要求我们按照以下步骤求出新的数组：

1. 寻找连续两个相邻的互质数（也就是最大公因数 GCD 为 1）
2. 将这两个相邻的互质数用两数的最小公倍数 LCM 替代
3. 回到第一步继续寻找直到没有互质数则直接结束返回数组

解题思路

这题的难点其实有三个：

1. 最大公因数 GCD 怎么求
2. 最小公倍数 LCM 怎么求
3. 如何处理好数组替换的操作

第一个难点，GCD 可以通过欧几里得算法来求解：gcd(a, b) = gcd(a, a mod b)，复杂度为 O(logM), M = min(a, b)

第二个难点，LCM 可以通过以下等式来获得：lcm(a, b) * gcd(a, b) = a * b => lcm(a, b) = a * b / gcd(a, b)

最后一个难点，我们只要维护一个栈，在遍历 nums 的时候只需要取栈顶元素与其对比后 push 对应的数字进栈即可

最后算法复杂度为 O(nlogM)

Javascript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var replaceNonCoprimes = function (nums) {
    const stack = []
    // gcd(a, b) = gcd(a, a mod b)
    const gcd = (a, b) => {
        while (b !== 0) {
            let temp = b
            b = a % b
            a = temp
        }
        return a
    }

    for(let num of nums) {
        while(stack.length > 0) {
            const top = stack[stack.length-1]
            const g = gcd(top, num)
            // if coprime
            if(g === 1) {
                break
            }
            stack.pop(top)
            // gcd(a, b) * lcm(a, b) = a * b => lcm(a, b) = a * b / gcd(a, b)
            num = num * top / g
        }
        stack.push(num)
    }

    return stack
};