leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一个整数数组 nums 。请你对数组执行下述操作:

  1. nums 中找出 任意 两个 相邻非互质 数。
  2. 如果不存在这样的数,终止 这一过程。
  3. 否则,删除这两个数,并 替换 为它们的 最小公倍数(Least Common Multiple,LCM)。
  4. 只要还能找出两个相邻的非互质数就继续 重复 这一过程。

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

生成的测试用例可以保证最终数组中的值 小于或者等于 108

两个数字 xy 满足 非互质数 的条件是:GCD(x, y) > 1 ,其中 GCD(x, y)xy最大公约数

 

示例 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
通过次数
7K
提交次数
19K
通过率
36.7%


相关企业

提示 1
Notice that the order of merging two numbers into their LCM does not matter so we can greedily merge elements to its left if possible.

提示 2
If a new value is formed, we should recursively check if it can be merged with the value to its left.

提示 3
To simulate the merge efficiently, we can maintain a stack that stores processed elements. When we iterate through the array, we only compare with the top of the stack (which is the value to its left).


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
nums =
[6,4,3,2,7,6,2]
Source