2197. 替换数组中的非互质数

来源第 283 场周赛 Q4难度困难分数2057

题目描述

给你一个整数数组 nums 。请你对数组执行下述操作：

从 nums 中找出任意两个相邻的 非互质 数。
如果不存在这样的数，终止这一过程。
否则，删除这两个数，并替换为它们的 最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续重复这一过程。

返回修改后得到的最终数组。可以证明的是，以任意顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 10⁸ 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
生成的测试用例可以保证最终数组中的值 小于或者等于 10⁸ 。

解法

方法一：栈

思考

相邻不互质则换成它们的 LCM，并继续与两侧合并，直到不能再合。三个数的合并与结合律无关，结果都是 LCM，因而可以只向左合。

栈顶与新来的数若不互质，就弹出并用 LCM 替换栈顶，循环直到互质或栈中不足两个。

每元素至多入出栈一次，中间 \(\gcd\) 的代价为对数。

如果存在三个相邻的数 \(x\), \(y\), \(z\) 可以进行合并，那么我们先合并 \(x\) 和 \(y\)，再合并 \(z\) 的结果，与先合并 \(y\) 和 \(z\)，再合并 \(x\) 的结果是一样的，结果均为 \(\textit{LCM}(x, y, z)\)。

因此，我们可以总是优先合并左侧相邻的数，再将合并后的结果与右侧相邻的数进行合并。

我们使用一个栈来模拟这个过程，遍历数组，对于每个数，我们将其入栈，然后不断检查栈顶的两个数是否互质，如果不互质，我们将这两个数出栈，然后将它们的最小公倍数入栈，直到栈顶的两个数互质，或者栈中元素小于两个。

最后栈中的元素即为最终结果。

时间复杂度 \(O(n \times \log M)\)，空间复杂度 \(O(n)\)。其中 \(M\) 为数组中的最大值。

Python3JavaC++GoTypeScriptRustC#

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stk = []
        for x in nums:
            stk.append(x)
            while len(stk) > 1:
                x, y = stk[-2:]
                g = gcd(x, y)
                if g == 1:
                    break
                stk.pop()
                stk[-1] = x * y // g
        return stk

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> stk = new ArrayList<>();
        for (int x : nums) {
            stk.add(x);
            while (stk.size() > 1) {
                x = stk.get(stk.size() - 1);
                int y = stk.get(stk.size() - 2);
                int g = gcd(x, y);
                if (g == 1) {
                    break;
                }
                stk.remove(stk.size() - 1);
                stk.set(stk.size() - 1, (int) ((long) x * y / g));
            }
        }
        return stk;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> stk;
        for (int x : nums) {
            stk.push_back(x);
            while (stk.size() > 1) {
                x = stk.back();
                int y = stk[stk.size() - 2];
                int g = __gcd(x, y);
                if (g == 1) {
                    break;
                }
                stk.pop_back();
                stk.back() = 1LL * x * y / g;
            }
        }
        return stk;
    }
};

func replaceNonCoprimes(nums []int) []int {
    stk := []int{}
    for _, x := range nums {
        stk = append(stk, x)
        for len(stk) > 1 {
            x = stk[len(stk)-1]
            y := stk[len(stk)-2]
            g := gcd(x, y)
            if g == 1 {
                break
            }
            stk = stk[:len(stk)-1]
            stk[len(stk)-1] = x * y / g
        }
    }
    return stk
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

function replaceNonCoprimes(nums: number[]): number[] {
    const gcd = (a: number, b: number): number => {
        if (b === 0) {
            return a;
        }
        return gcd(b, a % b);
    };
    const stk: number[] = [];
    for (let x of nums) {
        stk.push(x);
        while (stk.length > 1) {
            x = stk.at(-1)!;
            const y = stk.at(-2)!;
            const g = gcd(x, y);
            if (g === 1) {
                break;
            }
            stk.pop();
            stk.pop();
            stk.push(((x * y) / g) | 0);
        }
    }
    return stk;
}

impl Solution {
    pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
        fn gcd(mut a: i64, mut b: i64) -> i64 {
            while b != 0 {
                let t = a % b;
                a = b;
                b = t;
            }
            a
        }

        let mut stk: Vec<i64> = Vec::new();
        for x in nums {
            stk.push(x as i64);
            while stk.len() > 1 {
                let x = *stk.last().unwrap();
                let y = stk[stk.len() - 2];
                let g = gcd(x, y);
                if g == 1 {
                    break;
                }
                stk.pop();
                let last = stk.last_mut().unwrap();
                *last = x / g * y;
            }
        }

        stk.into_iter().map(|v| v as i32).collect()
    }
}

public class Solution {
    public IList<int> ReplaceNonCoprimes(int[] nums) {
        long Gcd(long a, long b) {
            while (b != 0) {
                long t = a % b;
                a = b;
                b = t;
            }
            return a;
        }

        var stk = new List<long>();
        foreach (int num in nums) {
            stk.Add(num);
            while (stk.Count > 1) {
                long x = stk[stk.Count - 1];
                long y = stk[stk.Count - 2];
                long g = Gcd(x, y);
                if (g == 1) {
                    break;
                }
                stk.RemoveAt(stk.Count - 1);
                stk[stk.Count - 1] = x / g * y;
            }
        }

        var ans = new List<int>();
        foreach (long v in stk) {
            ans.Add((int)v);
        }
        return ans;
    }
}

2197. 替换数组中的非互质数

题目描述

解法

方法一：栈

评论