难度: Medium
Submission
运行时间: 26 ms
内存: 16.2 MB
from math import gcd
class Solution:
def minimumSplits(self, nums: List[int]) -> int:
ans=1
n=len(nums)
pre=0
for i in range(1,n):
new=gcd(nums[i],nums[i-1])
if not pre:
pre=new
else:
pre=gcd(new,pre)
if pre==1:
ans+=1
pre=0
return ans
Explain
此题解采用贪心算法，通过计算连续子数组的最大公约数（GCD）来决定是否需要分割。初始化答案为1，表示至少一个不分割的子数组。遍历数组，使用变量`pre`记录前一个位置的GCD。对于每对相邻元素，计算它们的GCD，然后与`pre`的GCD更新`pre`。如果在某个位置`pre`变为1，说明到目前为止的子数组无法满足最大公约数大于1的要求，需要分割，将答案`ans`加1并重置`pre`。最后返回`ans`作为最少的分割次数。
时间复杂度: O(n log n)
空间复杂度: O(1)
from math import gcd
class Solution:
def minimumSplits(self, nums: List[int]) -> int:
ans = 1 # 初始分割数设为1，至少一个子数组
n = len(nums)
pre = 0 # 用于记录前一个GCD结果
for i in range(1, n):
new = gcd(nums[i], nums[i-1]) # 计算当前和前一个数的GCD
if not pre:
pre = new # 若pre为0，则初始化为new
else:
pre = gcd(new, pre) # 更新pre为当前GCD与pre的GCD
if pre == 1:
ans += 1 # 如果GCD变为1，需要分割，增加分割数
pre = 0 # 重置pre
return ans # 返回最少分割次数
Explore
在此题解中，每次`pre`变为1时进行分割，并重置`pre`为0，这意味着对接下来的元素重新开始计算GCD。这种方式实际上是保守的，因为它确保了每个分割后的子数组内部GCD大于1。重置`pre`并不会漏掉情况，而是确保从当前点重新开始计算，每个子数组内部都满足条件。这种方法可能导致分割次数稍多，但保证了结果的正确性。
贪心算法在此问题中的使用源于其简单和直观性——通过局部最优选择（即立即分割GCD为1的子数组），试图达成全局最优的分割策略。与动态规划相比，贪心算法通常更快，因为它不需要考虑所有可能的分割方案，减少了计算量。然而，贪心算法的劣势是它可能不总能得到最优解，尤其是在更复杂或有多种可能分割策略的问题中。在本题中，贪心算法足以解决问题，并提供了有效的解决方案。
如果输入数组的所有元素的GCD为1，这意味着任何子数组的最大公约数都无法大于1。题解中的算法通过初始化`ans`为1并逐个检查子数组，确保每次`pre`变为1时分割。在所有元素的GCD为1的情况下，算法会在每次尝试合并新元素后进行分割，因此`ans`会等于数组的长度。这种处理是正确的，因为每个单独的元素（作为长度为1的子数组）是不可能有大于1的GCD的。
在计算GCD时，如果其中一个数为0，则GCD等于另一个非零数的绝对值（由GCD的数学定义决定）。在题解的算法中，如果数组中存在0，其与任何数的GCD将是另一数的绝对值。这在算法中是自动处理的，因为Python的`gcd`函数能够正确处理0。因此，算法中不需要特殊处理包含0的情况。