题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
premium lock icon相关企业
提示

给你一个整数数组 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
通过次数
7,194/19.4K
通过率
37.1%


icon
相关企业

提示 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)
💡 讨论区规则

1. 请不要在评论区发表题解!

2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。

3. 如果你需要整理题解思路,获得反馈从而进阶提升,可以去题解区进行。

暂无评论

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
nums =
[6,4,3,2,7,6,2]
Source