替换数组中的非互质数

难度: Hard

给你一个整数数组 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⁸ 。

Submission

运行时间: 152 ms

内存: 29.9 MB

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]: 
        def re(nums):
            nums = nums[::-1]
            n = len(nums)
            res = nums[0]
            ans = []
            for i in range(1,len(nums)):
                k = gcd(res,nums[i])
                if k == 1:
                    ans.append(res)
                    res = nums[i]
                else:
                    res *= nums[i] // k
            ans.append(res)
            return ans
        
        for i in range(10):
            a = len(nums)
            nums = re(nums)
            if a == len(nums):
                if i % 2 == 1:
                    return nums
                else: 
                    return nums[::-1]

Explain

题解的思路是反复使用一个辅助函数 `re` 来处理数组，直到数组不再发生变化或者达到一定的迭代次数。辅助函数 `re` 的作用是从数组的末尾开始，逐个检查相邻的两个数是否互质，如果不是，则用它们的最小公倍数替换，直到数组头部。这种从后向前的处理方式是为了避免在处理过程中发生的元素替换影响到后续的处理。每次迭代后，都会检查数组长度是否发生变化，如果没有变化，则说明没有更多的非互质数对可以替换，处理过程结束。由于每次处理可能会改变数组的顺序，因此最后根据迭代次数的奇偶性决定是否需要反转数组以得到最终结果。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]: 
        def re(nums):
            nums = nums[::-1]  # 反转数组
            n = len(nums)
            res = nums[0]
            ans = []
            for i in range(1, len(nums)):
                k = gcd(res, nums[i])  # 计算当前结果与下一个数的最大公约数
                if k == 1:
                    ans.append(res)  # 如果互质，将当前结果加入答案数组
                    res = nums[i]  # 更新当前结果为下一个数
                else:
                    res *= nums[i] // k  # 如果不互质，更新当前结果为最小公倍数
            ans.append(res)
            return ans  # 返回处理后的数组
        
        for i in range(10):
            a = len(nums)
            nums = re(nums)  # 对数组进行处理
            if a == len(nums):  # 如果数组长度未变，说明没有更多非互质数对可以替换
                if i % 2 == 1:
                    return nums  # 如果迭代次数为奇数，直接返回数组
                else: 
                    return nums[::-1]  # 如果迭代次数为偶数，返回反转后的数组

Explore

从数组的末尾开始处理是因为在处理过程中，替换操作可能会影响到已经处理过的元素。如果从头部开始处理，每次替换可能会影响到后续的元素处理逻辑。而从末尾开始处理可以确保在处理当前元素时，该元素之前的部分已经被处理并确定下来，不会因为之后的操作而发生变化。这种方式有助于减少处理过程中的复杂性和潜在错误。

迭代次数固定为10次可能是基于经验或者在一般情况下的充分迭代次数假设。确实，存在特定的情况下，10次迭代仍可能无法达到最终数组状态，特别是在数组长度较大或数组中的数字范围较广时。在实际应用中，这个迭代次数可能需要根据具体问题的数据特性进行调整，以确保算法的正确性和效率。

使用`gcd`函数后计算最小公倍数确实可能导致处理结果中的数值快速增大，尤其是在非互质的数字较大时。由于最小公倍数是两个数的乘积除以它们的最大公约数，这可能导致结果数组中的数字迅速增长。这种增长会对计算性能产生影响，因为更大的数字需要更多的计算资源来处理。此外，数值的快速增长还可能导致整数溢出的问题，尤其是在编程语言中整数类型有固定上限的情况下。

这种偶奇次数的处理逻辑基于每次迭代后数组反转的操作。每次对数组进行`re`函数处理时，数组会先被反转，处理完成后再返回。因此，如果进行了奇数次迭代，最后一次处理后的数组相比原始数组是反转状态；如果进行了偶数次迭代，最后一次处理后的数组相比原始数组则是正常顺序。为了确保返回的数组与初始数组的顺序一致，需要根据迭代次数的奇偶性来决定是否对最终的数组进行反转。