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

Hard

题目描述

给你一个整数数组 nums。请你执行下述步骤：

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

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

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

如果 GCD(x, y) > 1，其中 GCD(x, y) 是 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。

解题思路

这道题的核心是不断合并相邻的非互质数，直到无法再合并为止。

算法思路：

栈的使用：由于合并操作会改变数组结构，我们可以使用栈来模拟这个过程。栈中存储已经处理过的元素。
贪心策略：从左到右遍历数组，对于每个元素，我们检查它是否能与栈顶元素合并（即是否非互质）。如果可以合并，就计算它们的LCM并替换栈顶元素。
递归检查：当我们得到一个新的LCM值后，需要继续检查这个新值是否能与栈中更前面的元素合并。这就形成了一个循环，直到无法再合并为止。
数学函数：
- GCD（最大公约数）：使用欧几里得算法
- LCM（最小公倍数）：LCM(a,b) = a * b / GCD(a,b)
- 非互质判断：GCD(a,b) > 1

算法流程：

初始化一个栈
遍历数组中的每个元素
对于当前元素，不断检查它是否能与栈顶元素合并
如果能合并，弹出栈顶，计算LCM，将LCM作为新的当前元素继续检查
如果不能合并，将当前元素压入栈
最后返回栈中的所有元素

这种方法的时间复杂度是O(n log max(nums))，其中log因子来自GCD计算。空间复杂度是O(n)。

代码实现

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<long long> stack;
        
        for (int num : nums) {
            long long current = num;
            
            while (!stack.empty() && gcd(stack.back(), current) > 1) {
                current = lcm(stack.back(), current);
                stack.pop_back();
            }
            
            stack.push_back(current);
        }
        
        vector<int> result;
        for (long long val : stack) {
            result.push_back(val);
        }
        
        return result;
    }
    
private:
    long long gcd(long long a, long long b) {
        while (b) {
            a %= b;
            swap(a, b);
        }
        return a;
    }
    
    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
};

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        import math
        
        stack = []
        
        for num in nums:
            current = num
            
            while stack and math.gcd(stack[-1], current) > 1:
                current = math.lcm(stack[-1], current)
                stack.pop()
            
            stack.append(current)
        
        return stack

public class Solution {
    public IList<int> ReplaceNonCoprimes(int[] nums) {
        List<long> stack = new List<long>();
        
        foreach (int num in nums) {
            long current = num;
            
            while (stack.Count > 0 && GCD(stack[stack.Count - 1], current) > 1) {
                current = LCM(stack[stack.Count - 1], current);
                stack.RemoveAt(stack.Count - 1);
            }
            
            stack.Add(current);
        }
        
        List<int> result = new List<int>();
        foreach (long val in stack) {
            result.Add((int)val);
        }
        
        return result;
    }
    
    private long GCD(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    private long LCM(long a, long b) {
        return a / GCD(a, b) * b;
    }
}

var replaceNonCoprimes = function(nums) {
    const stack = [];
    
    for (let num of nums) {
        let current = num;
        
        while (stack.length > 0 && gcd(stack[stack.length - 1], current) > 1) {
            current = lcm(stack[stack.length - 1], current);
            stack.pop();
        }
        
        stack.push(current);
    }
    
    return stack;
};

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

function lcm(a, b) {
    return Math.floor(a / gcd(a, b) * b);
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大O表示法
时间复杂度	O(n log(max(nums)))
空间复杂度	O(n)

说明：

时间复杂度：每个元素最多被处理常数次，GCD计算的复杂度是O(log(min(a,b)))
空间复杂度：栈最多存储所有原始元素

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目