分割数组使乘积互质

难度: Hard

给你一个长度为 n 的整数数组 nums ，下标从 0 开始。

如果在下标 i 处分割数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割有效。

例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因为 i == n - 1 。

返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。

当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。

示例 1：

输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。

示例 2：

输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。

提示：

n == nums.length
1 <= n <= 10⁴
1 <= nums[i] <= 10⁶

Submission

运行时间: 376 ms

内存: 48.3 MB

ma = 10**6

def get_primes(M):
    f = [1]*M
    for i in range(2,isqrt(M)+1):
        if f[i]:
            f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
    return [i for i in range(2,M) if f[i]]

primes = get_primes(isqrt(ma)+1)

@cache
def factor(x):
    ct = Counter()
    for p in primes:
        while x%p==0:
            x//=p
            ct[p] += 1
    if x>1:
        ct[x] += 1
    return ct

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        n = len(nums)
        d = {p:i for i in range(n) for p in factor(nums[i])}
        r = 0
        for i in range(n-1):
            for p in factor(nums[i]):
                r = max(r,d[p])
            if r==i:
                return i
        return -1

Explain

本题解采用了一种基于数论和质因数分解的方法来寻找有效的分割点。首先，创建一个质数列表，用于对数组中的每个元素进行质因数分解。然后，利用一个字典记录每个质因数最后一次出现的位置。接着，遍历数组，对于每个元素，更新其质因数的最后出现位置，并检查当前位置是否是有效的分割点。如果当前位置与记录的最大质因数位置相等，说明该位置是一个有效的分割点，因为在此之前的所有元素的乘积与之后的元素的乘积不共享任何质因数，因而互质。如果遍历完成后没有找到有效分割点，则返回-1。

时间复杂度: O(n log M)

空间复杂度: O(n log M)

from math import isqrt
from functools import cache
from collections import Counter

# 计算不超过M的所有质数
ma = 10**6
def get_primes(M):
    f = [1]*M
    for i in range(2, isqrt(M)+1):
        if f[i]:
            f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
    return [i for i in range(2, M) if f[i]]

primes = get_primes(isqrt(ma)+1)

# 使用质数列表对x进行质因数分解
@cache
def factor(x):
    ct = Counter()
    for p in primes:
        while x % p == 0:
            x //= p
            ct[p] += 1
    if x > 1:
        ct[x] += 1
    return ct

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        n = len(nums)
        # 记录每个质因数最后出现的位置
        d = {p: i for i in range(n) for p in factor(nums[i])}
        r = 0
        for i in range(n-1):
            # 更新质因数的最后位置
            for p in factor(nums[i]):
                r = max(r, d[p])
            # 检查当前位置是否为有效的分割点
            if r == i:
                return i
        return -1

Explore

在实现中，`ma`代表数组中元素的最大值，该值是估计的或基于问题的上下文确定的。生成质数列表的范围需要覆盖到数组中所有元素的可能质因数，因此需要至少包括到数组中最大元素的平方根。这是因为一个数的最大质因数不会超过其平方根。如果题目中给出了元素的最大范围，我们可以直接使用这一信息。如果没有给出，可能需要先遍历数组确定最大元素。在这个题解中，假设`ma`为10^6，是基于一般情况或题目设定的典型数据范围。

使用`cache`装饰器来优化质因数分解的函数在数组中存在重复元素或多个元素共享相同质因数时最有效。这种缓存机制可以避免对相同值重复进行质因数分解，从而节省计算时间。然而，缓存也可能导致大量内存使用，尤其是当处理大数据集时。如果质因数分解的数据非常多样，那么缓存可能会存储大量结果，这可能成为性能瓶颈，特别是在内存有限的环境中。

在题解中使用字典推导式初始化质因数字典`d`是为了记录每个质因数在数组中的最后一次出现的位置。这种方法确实意味着如果一个质因数在多个位置出现，字典中的记录会被更新为该质因数最后一次出现的位置。这是因为在分割点检查中，我们需要知道质因数出现的最后位置来确定是否可以在某个点进行分割。如果一个质因数的最后位置在当前检查点之后，那么当前点不能作为有效的分割点。因此，覆盖之前的记录是符合逻辑的，以确保我们总是有最新的位置信息。