leetcode 2197. Replace Non-Coprime Numbers in Array（python）

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情

前言

这是 Weekly Contest 283 的第四题，我们可以借用数学方法来解题，难度 Hard ，其实做出来的人不少。

描述

You are given an array of integers nums. Perform the following steps:

• Find any two adjacent numbers in nums that are non-coprime.
• If no such numbers are found, stop the process.
• Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
• Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 10^8.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.
复制代码

Note:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
The test cases are generated such that the values in the final array are less than or equal to 10^8.

解析

根据题意，这道题给出了一个整数数组 nums ，然后执行下面的操作：

• 找到 nums 中任意两个挨着的非互质元素
• 将找到的这两个挨着的非互质元素删掉，替换成他们的最小公倍数
• 只要在 nums 中有两个挨着的非互质元素就重复上面的过程
• 如果找不到这样的上面说的情况就停止操作

最后题目要求我们返回经过上述操作变换之后最终得到 nums ，而且题目也给出了证明结论，以任意顺序替换相邻的非互质数将会得到相同的结果。题目最后还给出了非互质的定义，就是两个数字的最大公约数大于 1 。

其实这道题当我看到的时候我有点又惊又喜，因为要解决这道题是要套用一个数学公式的，而在做题之前我老婆在考研准备数学，刚好看到了这个公式，那就是有两个数字 a 和 b ，那么 GDC(a,b) * LCM(a,b) = a * b ，换句话说就是两个数字的最大公约数与最小公倍数的积等于两个数字的乘积。正好可以通用在这道题上，你说凑巧不凑巧。

其实有了上面的公式，解题就很简单了，定义一个 result 用来存放结果，我们按照从左往右的顺序不断遍历 nums 中的第一个元素 n ，只要 n 与 result[-1] 两个数字是非互质的，我们就不断循环去执行找它们两个最小公倍数的操作，直到是互质的跳出循环，将 n 加入结果中，然后去对下一个元素 n 进行同样的操作，最后返回 result 即可。

时间复杂度为 O(N*logN) ，因为找 gcd 需要 O(logN) ，空间复杂度为 O(N)。我本来自己写了 gcd 函数，但是超时了，所以干脆直接用了内置函数，顺利通过。

解答

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        result = []
        for n in nums:
            while True:
                GCD = gcd(result[-1] if result else 1, n)
                if GCD==1:break
                n = n * result.pop() // GCD
            result.append(n)
        return result
复制代码

运行结果

71 / 71 test cases passed.
Status: Accepted
Runtime: 3017 ms
Memory Usage: 30.6 MB
复制代码

原题链接

leetcode.com/contest/wee…

您的支持是我最大的动力