LeetCode 题解工作台
替换数组中的非互质数
给你一个整数数组 nums 。请你对数组执行下述操作： 从 nums 中找出 任意 两个 相邻 的 非互质 数。 如果不存在这样的数， 终止 这一过程。 否则，删除这两个数，并 替换 为它们的 最小公倍数 （Least Common Multiple，LCM）。 只要还能找出两个相邻的非互质数就继续…
4
题型
7
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
如果存在三个相邻的数 , , 可以进行合并，那么我们先合并 和 ，再合并 的结果，与先合并 和 ，再合并 的结果是一样的，结果均为 $\textit{LCM}(x, y, z)$。 因此，我们可以总是优先合并左侧相邻的数，再将合并后的结果与右侧相邻的数进行合并。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个整数数组 nums 。请你对数组执行下述操作：
- 从
nums中找出 任意 两个 相邻 的 非互质 数。 - 如果不存在这样的数，终止 这一过程。
- 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
- 只要还能找出两个相邻的非互质数就继续 重复 这一过程。
返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 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 <= 1051 <= nums[i] <= 105- 生成的测试用例可以保证最终数组中的值 小于或者等于
108。
解题思路
方法一：栈
如果存在三个相邻的数 , , 可以进行合并，那么我们先合并 和 ，再合并 的结果，与先合并 和 ，再合并 的结果是一样的，结果均为 。
因此，我们可以总是优先合并左侧相邻的数，再将合并后的结果与右侧相邻的数进行合并。
我们使用一个栈来模拟这个过程，遍历数组，对于每个数，我们将其入栈，然后不断检查栈顶的两个数是否互质，如果不互质，我们将这两个数出栈，然后将它们的最小公倍数入栈，直到栈顶的两个数互质，或者栈中元素小于两个。
最后栈中的元素即为最终结果。
时间复杂度 ，空间复杂度 。其中 为数组中的最大值。
class Solution:
def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
stk = []
for x in nums:
stk.append(x)
while len(stk) > 1:
x, y = stk[-2:]
g = gcd(x, y)
if g == 1:
break
stk.pop()
stk[-1] = x * y // g
return stk
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of merges, which is at most proportional to the array length, as each merge reduces the effective number of elements. Space complexity is O(n) due to the stack storing processed numbers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if you are correctly handling consecutive merges in the stack.
- question_mark
Ask how your approach ensures that the final array is unique regardless of merge order.
- question_mark
Consider edge cases where numbers are prime or repeated in sequence.
常见陷阱
外企场景- error
Not repeatedly merging with the stack top after a replacement can yield incorrect final arrays.
- error
Using inefficient GCD or LCM calculations may cause timeouts on large arrays.
- error
Failing to maintain the stack order can break the left-to-right merge consistency required by the problem.
进阶变体
外企场景- arrow_right_alt
Replace adjacent numbers with LCM if their sum is not prime, instead of coprime condition.
- arrow_right_alt
Merge adjacent non-coprime numbers but return the sum of the final array instead of the array itself.
- arrow_right_alt
Apply the same merging process on a circular array where the first and last elements are considered adjacent.