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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

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

方法一：栈

思路与算法

由于题目不加证明地给出了「任意顺序替换相邻的非互质数都可以得到相同的结果」，因此我们可以从前往后进行替换。

我们可以使用一个栈来进行替换操作。具体地，我们对数组 nums 进行一次遍历。当遍历到 nums}[i] 时。在其被放入栈顶前，我们重复进行替换操作，直到 nums}[i] 和栈顶的元素互质，或者栈为空为止。此时，我们再将替换完成的 nums}[i] 放入栈顶。

最终栈底到栈顶的元素序列即为答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans;
        for (int num: nums) {
            while (!ans.empty()) {
                int g = gcd(ans.back(), num);
                if (g > 1) {
                    num = ans.back() / g * num;
                    ans.pop_back();
                }
                else {
                    break;
                }
            }
            ans.push_back(num);
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        ans = list()
        for num in nums:
            while ans:
                g = math.gcd(ans[-1], num)
                if g > 1:
                    num = ans[-1] // g * num
                    ans.pop()
                else:
                    break
            ans.append(num)
        
        return ans

复杂度分析

  • 时间复杂度：O(n \log C)，其中 n 是数组 nums 的长度，C 是数组 nums 中的数据范围，O(\log C) 即为单次计算最大公约数需要的时间。

  • 空间复杂度：O(1)。这里不计入返回值需要使用的空间。

 Comments
On this page
2197-替换数组中的非互质数