Qwen模型 LeetCode 2584. 分割数组使乘积互质 Java实现
哇！这道2584题超有意思的，让我来给你讲讲我的解法思路~ 这道题就像是在玩"化学实验"，我们要把数组分成两部分，让它们的"化学成分"（质因数）完全不重叠！
题目要求找到最小的分割点，使得左边所有数的乘积和右边所有数的乘积互质。互质就是说它们没有共同的质因数，就像两个陌生人一样没有任何交集。
```java
import java.util.*;
public class Solution {
public int findValidSplit(int[] nums) {
int n = nums.length;
// 特判：只有一个元素的情况
if (n == 1) return -1;
// 记录每个质因数最后出现的位置
Map<Integer, Integer> lastOccurrence = new HashMap<>();
// 预处理：找出每个位置的所有质因数，并记录它们最后出现的位置
for (int i = 0; i < n; i++) {
int num = nums[i];
Set<Integer> 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];
Set<Integer> primeFactors = getPrimeFactors(num);
// 更新当前需要覆盖的最远位置
for (int factor : primeFactors) {
maxReach = Math.max(maxReach, lastOccurrence.get(factor));
}
// 如果当前位置已经可以作为分割点
if (i >= maxReach) {
return i;
}
}
return -1;
}
// 获取一个数的所有质因数（去重）
private Set<Integer> getPrimeFactors(int num) {
Set<Integer> factors = new HashSet<>();
// 处理因子2
if (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是不同质因数的个数。
你觉得这个思路怎么样？要不要我再给你讲讲其他类似的"区间覆盖"问题？这类题目在面试中还挺常见的呢！😄