README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/2400-2499/2436.Minimum%20Split%20Into%20Subarrays%20With%20GCD%20Greater%20Than%20One/README.md	贪心 数组 数学 动态规划 数论

2436. 使子数组最大公约数大于一的最小分割数 🔒

English Version

题目描述

给定一个由正整数组成的数组 nums。

将数组拆分为 一个或多个 互相不覆盖的子数组，如下所示:

• 数组中的每个元素都 只属于一个 子数组，并且
• 每个子数组元素的 最大公约数 严格大于 1。

返回拆分后可获得的子数组的最小数目。

注意:

• 子数组的 最大公约数 是能将子数组中所有元素整除的最大正整数。

• 子数组 是数组的连续部分。

 

示例 1:

输入: nums = [12,6,3,14,8]
输出: 2
解释: 我们可以把数组分成子数组:[12,6,3] 和 [14,8]。
- 12、6、3 的最大公约数是 3，严格大于 1。
- 14 和 8 的最大公约数是 2，严格来说大于 1。
可以看出，如果不拆分数组将使最大公约数 = 1。

示例 2:

输入: nums = [4,12,6,14]
输出: 1
解释: 我们可以将数组拆分为一个子数组，即整个数组。

 

提示:

• 1 <= nums.length <= 2000
• 2 <= nums[i] <= 109

解法

方法一：贪心 + 数学

对于数组中的每个元素，如果它与前面的元素的最大公约数为 $1$，那么它需要作为一个新的子数组的第一个元素。否则，它可以与前面的元素放在同一个子数组中。

因此，我们先初始化一个变量 $g$，表示当前子数组的最大公约数。初始时 $g=0$，答案变量 $ans=1$。

接下来，我们从前往后遍历数组，维护当前子数组的最大公约数 $g$。如果当前元素 $x$ 与 $g$ 的最大公约数为 $1$，那么我们需要将当前元素作为一个新的子数组的第一个元素，因此，答案加 $1$，并将 $g$ 更新为 $x$。否则，当前元素可以与前面的元素放在同一个子数组中。继续遍历数组，直到遍历结束。

时间复杂度 $O(n \times \log m)$，其中 $n$ 和 $m$ 分别是数组的长度和数组中元素的最大值。空间复杂度 $O(1)$。

Python3

class Solution:
    def minimumSplits(self, nums: List[int]) -> int:
        ans, g = 1, 0
        for x in nums:
            g = gcd(g, x)
            if g == 1:
                ans += 1
                g = x
        return ans

Java

class Solution {
    public int minimumSplits(int[] nums) {
        int ans = 1, g = 0;
        for (int x : nums) {
            g = gcd(g, x);
            if (g == 1) {
                ++ans;
                g = x;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

C++

class Solution {
public:
    int minimumSplits(vector<int>& nums) {
        int ans = 1, g = 0;
        for (int x : nums) {
            g = gcd(g, x);
            if (g == 1) {
                ++ans;
                g = x;
            }
        }
        return ans;
    }
};

Go

func minimumSplits(nums []int) int {
	ans, g := 1, 0
	for _, x := range nums {
		g = gcd(g, x)
		if g == 1 {
			ans++
			g = x
		}
	}
	return ans
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

TypeScript

function minimumSplits(nums: number[]): number {
    let ans = 1;
    let g = 0;
    for (const x of nums) {
        g = gcd(g, x);
        if (g == 1) {
            ++ans;
            g = x;
        }
    }
    return ans;
}

function gcd(a: number, b: number): number {
    return b ? gcd(b, a % b) : a;
}