Hard

题目描述

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

当 0 <= i <= n - 2 时，如果满足前 i + 1 个元素的乘积和剩余元素的乘积互质，那么下标 i 处的分割就是 有效的。

  • 例如，如果 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^4
  • 1 <= nums[i] <= 10^6

解题思路

解题思路

这道题要求找到一个分割点，使得左侧所有数字的乘积与右侧所有数字的乘积互质（最大公约数为1）。

核心观察： 两个数互质当且仅当它们没有共同的质因子。因此我们不需要计算实际的乘积，只需要跟踪质因子的分布即可。

算法步骤：

  1. 质因数分解： 对每个数字进行质因数分解，记录每个质因子的出现位置
  2. 区间维护： 对于每个质因子，记录它在数组中第一次和最后一次出现的位置
  3. 合并区间： 如果一个质因子在位置i第一次出现，在位置j最后一次出现，那么区间[i,j]内的所有数字都不能被分开（因为它们共享这个质因子）
  4. 寻找分割点： 从左到右扫描，维护当前必须包含的最大右边界。当扫描到的位置等于当前右边界时，说明找到了一个有效的分割点

时间复杂度优化： 使用高效的质因数分解方法，预处理最小质因子数组，使分解过程更快。

这种方法避免了直接计算大数乘积，也避免了重复的GCD计算，是最优解法。

代码实现

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return -1;
        
        // 预处理最小质因子
        vector<int> spf(1000001);
        for (int i = 1; i <= 1000000; i++) spf[i] = i;
        for (int i = 2; i * i <= 1000000; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= 1000000; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        
        unordered_map<int, int> firstOcc, lastOcc;
        
        // 记录每个质因子的第一次和最后一次出现位置
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            unordered_set<int> factors;
            
            while (num > 1) {
                int p = spf[num];
                factors.insert(p);
                while (num % p == 0) {
                    num /= p;
                }
            }
            
            for (int factor : factors) {
                if (firstOcc.find(factor) == firstOcc.end()) {
                    firstOcc[factor] = i;
                }
                lastOcc[factor] = i;
            }
        }
        
        // 找最小的有效分割点
        int maxEnd = -1;
        for (int i = 0; i < n - 1; i++) {
            int num = nums[i];
            unordered_set<int> factors;
            
            while (num > 1) {
                int p = spf[num];
                factors.insert(p);
                while (num % p == 0) {
                    num /= p;
                }
            }
            
            for (int factor : factors) {
                maxEnd = max(maxEnd, lastOcc[factor]);
            }
            
            if (maxEnd == i) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return -1
        
        # 预处理最小质因子
        spf = list(range(1000001))
        i = 2
        while i * i <= 1000000:
            if spf[i] == i:
                j = i * i
                while j <= 1000000:
                    if spf[j] == j:
                        spf[j] = i
                    j += i
            i += 1
        
        first_occ = {}
        last_occ = {}
        
        # 记录每个质因子的第一次和最后一次出现位置
        for i in range(n):
            num = nums[i]
            factors = set()
            
            while num > 1:
                p = spf[num]
                factors.add(p)
                while num % p == 0:
                    num //= p
            
            for factor in factors:
                if factor not in first_occ:
                    first_occ[factor] = i
                last_occ[factor] = i
        
        # 找最小的有效分割点
        max_end = -1
        for i in range(n - 1):
            num = nums[i]
            factors = set()
            
            while num > 1:
                p = spf[num]
                factors.add(p)
                while num % p == 0:
                    num //= p
            
            for factor in factors:
                max_end = max(max_end, last_occ[factor])
            
            if max_end == i:
                return i
        
        return -1

public class Solution {
    public int FindValidSplit(int[] nums) {
        int n = nums.Length;
        if (n == 1) return -1;
        
        // 预处理最小质因子
        int[] spf = new int[1000001];
        for (int i = 1; i <= 1000000; i++) spf[i] = i;
        for (int i = 2; i * i <= 1000000; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= 1000000; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        
        Dictionary<int, int> firstOcc = new Dictionary<int, int>();
        Dictionary<int, int> lastOcc = new Dictionary<int, int>();
        
        // 记录每个质因子的第一次和最后一次出现位置
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            HashSet<int> factors = new HashSet<int>();
            
            while (num > 1) {
                int p = spf[num];
                factors.Add(p);
                while (num % p == 0) {
                    num /= p;
                }
            }
            
            foreach (int factor in factors) {
                if (!firstOcc.ContainsKey(factor)) {
                    firstOcc[factor] = i;
                }
                lastOcc[factor] = i;
            }
        }
        
        // 找最小的有效分割点
        int maxEnd = -1;
        for (int i = 0; i < n - 1; i++) {
            int num = nums[i];
            HashSet<int> factors = new HashSet<int>();
            
            while (num > 1) {
                int p = spf[num];
                factors.Add(p);
                while (num % p == 0) {
                    num /= p;
                }
            }
            
            foreach (int factor in factors) {
                maxEnd = Math.Max(maxEnd, lastOcc[factor]);
            }
            
            if (maxEnd == i) {
                return i;
            }
        }
        
        return -1;
    }
}

var findValidSplit = function(nums) {
    const n = nums.length;
    
    function getPrimeFactors(num) {
        const factors = new Set();
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) {
                factors.add(i);
                while (num % i === 0) {
                    num /= i;
                }
            }
        }
        if (num > 1) factors.add(num);
        return factors;
    }
    
    // Get prime factors for each number
    const primeFactors = nums.map(getPrimeFactors);
    
    // For each position, track which prime factors are in left and right parts
    const leftFactors = new Set();
    const rightFactors = new Set();
    
    // Initialize right factors with all factors
    for (let i = 0; i < n; i++) {
        for (const factor of primeFactors[i]) {
            rightFactors.add(factor);
        }
    }
    
    for (let i = 0; i < n - 1; i++) {
        // Move factors from right to left
        for (const factor of primeFactors[i]) {
            leftFactors.add(factor);
        }
        
        // Check if we can remove factors from right
        const newRightFactors = new Set();
        for (let j = i + 1; j < n; j++) {
            for (const factor of primeFactors[j]) {
                newRightFactors.add(factor);
            }
        }
        
        // Check if left and right have any common factors
        let hasCommonFactor = false;
        for (const factor of leftFactors) {
            if (newRightFactors.has(factor)) {
                hasCommonFactor = true;
                break;
            }
        }
        
        if (!hasCommonFactor) {
            return i;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n√M + M log log M)
空间复杂度O(M + n)

其中 n 是数组长度，M 是数组中元素的最大值（10^6）。预处理最小质因子的时间复杂度为 O(M log log M)，对每个数字进行质因数分解的时间复杂度为 O(√M)。

相关题目