class Solution {
public:
vector<int> replaceNonCoprimes(vector<int>& nums) {
}
};
2197. 替换数组中的非互质数
给你一个整数数组 nums 。请你对数组执行下述操作：
nums 中找出 任意 两个 相邻 的 非互质 数。返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
生成的测试用例可以保证最终数组中的值 小于或者等于 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] <= 105108 。原站题解
rust 解法, 执行用时: 36 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-14 00:37:42
impl Solution {
pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
fn gcd(a: i32, b: i32)->i32{
if b == 0{
return a;
}else{
return gcd(b, a%b);
}
}
let mut ans = vec![nums[0]];
for &num in nums.iter().skip(1){
ans.push(num);
loop{
if ans.len() <= 1 {
break;
}
let mut x = ans[ans.len() -1];
let mut y = ans[ans.len() -2];
let g = gcd(x, y);
if g == 1{
break;
}
ans.pop();
let top = ans.last_mut().unwrap();
*top = *top /g * x;
}
}
ans
}
}
golang 解法, 执行用时: 156 ms, 内存消耗: 8.9 MB, 提交时间: 2023-09-14 00:37:18
func replaceNonCoprimes(nums []int) []int {
s := []int{}
for _, num := range nums {
s = append(s, num)
for len(s) > 1 {
x, y := s[len(s)-1], s[len(s)-2]
g := gcd(x, y)
if g == 1 {
break
}
s = s[:len(s)-1]
s[len(s)-1] *= x / g
}
}
return s
}
func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }
cpp 解法, 执行用时: 148 ms, 内存消耗: 118.4 MB, 提交时间: 2023-09-14 00:37:06
class Solution {
public:
vector<int> replaceNonCoprimes(vector<int> &nums) {
vector<int> s;
for (int num : nums) {
s.push_back(num);
while (s.size() > 1) {
int x = s.back(), y = s[s.size() - 2];
int g = gcd(x, y);
if (g == 1) break;
s.pop_back();
s.back() *= x / g;
}
}
return s;
}
};
java 解法, 执行用时: 36 ms, 内存消耗: 61.8 MB, 提交时间: 2023-09-14 00:36:54
class Solution {
public List<Integer> replaceNonCoprimes(int[] nums) {
var s = new ArrayList<Integer>();
for (var num : nums) {
s.add(num);
while (s.size() > 1) {
var x = s.get(s.size() - 1);
var y = s.get(s.size() - 2);
var g = gcd(x, y);
if (g == 1) break;
s.remove(s.size() - 1);
s.set(s.size() - 1, x / g * y);
}
}
return s;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
python3 解法, 执行用时: 292 ms, 内存消耗: 29.9 MB, 提交时间: 2023-09-14 00:36:40
class Solution:
def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
s = []
for num in nums:
s.append(num)
while len(s) > 1:
x, y = s[-1], s[-2]
g = gcd(x, y)
if g == 1: break
s.pop()
s[-1] *= x // g
return s