哇!JavaScript版本来啦~这道题用JS写起来特别优雅,让我给你展示一个清晰又高效的实现!
```javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findValidSplit = function(nums) {
const n = nums.length;
if (n === 1) return -1;
// 记录每个质因数最后出现的位置
const lastOccurrence = new Map();
// 预处理:找出每个位置的所有质因数,并记录最后出现位置
for (let i = 0; i < n; i++) {
const primeFactors = getPrimeFactors(nums[i]);
for (const factor of primeFactors) {
lastOccurrence.set(factor, i);
}
}
// 贪心扫描:维护当前需要覆盖的最远位置
let maxReach = 0;
for (let i = 0; i < n - 1; i++) {
const primeFactors = getPrimeFactors(nums[i]);
// 更新当前需要覆盖的最远位置
for (const factor of primeFactors) {
maxReach = Math.max(maxReach, lastOccurrence.get(factor));
}
// 如果当前位置可以作为分割点
if (i >= maxReach) {
return i;
}
}
return -1;
};
// 获取一个数的所有质因数(去重)
function getPrimeFactors(num) {
const factors = new Set();
// 处理因子2
if (num % 2 === 0) {
factors.add(2);
while (num % 2 === 0) {
num = Math.floor(num / 2);
}
}
// 处理奇数因子
for (let i = 3; i * i <= num; i += 2) {
if (num % i === 0) {
factors.add(i);
while (num % i === 0) {
num = Math.floor(num / i);
}
}
}
// 如果剩下的数大于1,说明它本身就是一个质数
if (num > 1) {
factors.add(num);
}
return factors;
}
```
嘿嘿,这个JS版本是不是看起来特别清爽?✨
**让我用个生活化的例子解释一下**:
想象你有一排彩色的糖果,每颗糖果都有自己的"颜色配方"(质因数)。你要在某个位置切一刀,让左边和右边的糖果没有任何共同的颜色。
比如数组 `[6, 10, 15]`:
- 6 = 2 × 3(红色+蓝色)
- 10 = 2 × 5(红色+绿色)
- 15 = 3 × 5(蓝色+绿色)
你看,红色从位置0延续到1,蓝色从0延续到2,绿色从1延续到2。所以我们要等到位置2之后才能切割,但数组只有3个元素,所以返回-1!
**JS实现的小技巧**:
- ✅ 用 `Set` 自动去重质因数,超方便!
- ✅ 用 `Map` 记录最后出现位置,查找O(1)
- ✅ `Math.floor()` 确保整数除法(虽然JS中 `/` 对整数结果没问题,但显式更好)
- ✅ 函数式风格,逻辑清晰易读
**时间复杂度**:O(n√m),其中m是数组中的最大值
**空间复杂度**:O(k),k是不同质因数的个数
你觉得这个思路怎么样?JS写算法题其实很舒服呢,特别是Set和Map这些数据结构用起来特别顺手!要不要再来一道类似的题目练练手?😄