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

题目描述

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

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

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

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

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

解题思路与题解

如果有三个相邻且可以合并的数 x,y,z，那么先合并 x 和 y 再合并 z，还是先合并 y 和 z 再合并 x，结果是一样的吗？

是一样的，由于 LCM 本质是质因数分解中质数的指数取最大值（见初等数论教材），对于 max(a,b,c) 来说，我们有

max(a,b,c)=max(max(a,b),c)=max(a,max(b,c))
所以 x,y,z 先合并 x,y 还是先合并 y,z 都可以。得到的结果均为 LCM(x,y,z)。

该结论可以推广到更多元素的情况。

据此，对于任意一种合并顺序，我们总是可以将该顺序重排成：

  • 优先选择最左边的能合并的相邻元素，将其合并。

这可以用栈模拟：

  1. 创建一个空栈。
  2. 从左到右遍历 nums。
  3. 设 x=nums[i]。如果栈不为空且 x 与栈顶不互质，那么弹出栈顶 y，更新 x 为 LCM(x,y)。循环直到栈为空或者 x 与栈顶互质。
  4. 把 x 入栈。
  5. 遍历结束，栈即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.List;

public class LeetCode2197 {

    public static List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> st = new ArrayList<>();
        for (int x : nums) {
            while (!st.isEmpty() && gcd(x, st.getLast()) > 1) {
                x = lcm(x, st.removeLast());
            }
            st.add(x);
        }
        return st;
    }

    private static int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }

    private static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    public static void main(String[] args) {
        System.out.println(replaceNonCoprimes(new int[]{2, 3, 4, 5, 7}));
        System.out.println(replaceNonCoprimes(new int[]{2, 2, 2, 2, 2}));
        System.out.println(replaceNonCoprimes(new int[]{2, 10, 2, 5, 10, 5}));
    }

}