日期: 2025 年 9 月 16 日

目标

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

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

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

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

两个数字 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^5
• 1 <= nums[i] <= 10^5
• 生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

思路

将数组 nums 中相邻的非互质的数用它们的最小公倍数替换，一直重复这一过程，返回最终的数组。

遍历数组，针对每一个 num 判断它与其左侧已处理的最后一个值（即 list 的最后一个元素）是否互质，如果不互质，将 num 替换为它们的最小公倍数，同时删除 list 最后一个元素，重复该过程，直到互质为止，最后将 num 加入 list。

代码

/**
 * @date 2025-09-16 8:45
 */
public class ReplaceNonCoprimes2197 {

    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int a : nums) {
            while (!list.isEmpty()) {
                int b = list.get(list.size() - 1);
                int g = gcd(a, b);
                if (g <= 1) {
                    break;
                }
                a = a / g * b;
                list.remove(list.size() - 1);
            }
            list.add(a);
        }
        return list;
    }

}

性能