哇这道2584题超有意思的让我来给你讲讲我的解法思路~ 这道题就像是在玩化学实验我们要把数组分成两部分让它们的化学成分质因数完全不重叠题目要求找到最小的分割点使得左边所有数的乘积和右边所有数的乘积互质。互质就是说它们没有共同的质因数就像两个陌生人一样没有任何交集。javaimport java.util.*;public class Solution {public int findValidSplit(int[] nums) {int n nums.length;// 特判只有一个元素的情况if (n 1) return -1;// 记录每个质因数最后出现的位置MapInteger, Integer lastOccurrence new HashMap();// 预处理找出每个位置的所有质因数并记录它们最后出现的位置for (int i 0; i n; i) {int num nums[i];SetInteger primeFactors getPrimeFactors(num);for (int factor : primeFactors) {lastOccurrence.put(factor, i);}}// 贪心扫描维护当前需要覆盖的最远位置int maxReach 0;for (int i 0; i n - 1; i) {int num nums[i];SetInteger primeFactors getPrimeFactors(num);// 更新当前需要覆盖的最远位置for (int factor : primeFactors) {maxReach Math.max(maxReach, lastOccurrence.get(factor));}// 如果当前位置已经可以作为分割点if (i maxReach) {return i;}}return -1;}// 获取一个数的所有质因数去重private SetInteger getPrimeFactors(int num) {SetInteger factors new HashSet();// 处理因子2if (num % 2 0) {factors.add(2);while (num % 2 0) {num / 2;}}// 处理奇数因子for (int i 3; i * i num; i 2) {if (num % i 0) {factors.add(i);while (num % i 0) {num / i;}}}// 如果剩下的数大于1说明它本身就是一个质数if (num 1) {factors.add(num);}return factors;}}嘿嘿这个解法的核心思想特别巧妙我把它叫做质因数覆盖区间法**想象一下**每个质因数就像一条彩带从它第一次出现的位置一直延伸到最后一次出现的位置。我们要找的分割点就是所有彩带都结束之后的位置**算法步骤**1. **预处理阶段**遍历整个数组找出每个质因数最后出现的位置2. **贪心扫描**从左到右走维护一个最远需要覆盖的位置3. **判断分割点**当我们的当前位置超过了所有已遇到质因数的最远位置时就可以分割啦举个例子[2, 3, 6, 5]- 质因数2出现在位置0和2最后在位置2- 质因数3出现在位置1和2最后在位置2- 质因数5出现在位置3最后在位置3当我们走到位置2时发现质因数2和3的最远位置都是2但这时候我们还没处理完因为位置2的6还包含了这些因子。只有当我们确保所有相关的质因数都不会再出现在右边时才能安全分割这个算法的时间复杂度大概是 O(n√m)其中m是数组中最大的数空间复杂度是O(k)k是不同质因数的个数。你觉得这个思路怎么样要不要我再给你讲讲其他类似的区间覆盖问题这类题目在面试中还挺常见的呢
