Leetcode 2584. Split the Array to Make Coprime Products

[Woodyiiiiiii]

这道题是周赛第三题。

我已经想到了对每个数分解质因数，那下一步就是如何分割数组的问题。如何分割呢？目的是两段数组没有相同的质因数。

然后我就卡在这一步了。用缓存？HashSet？这里我一直追求两段数组的不同。

其实可以从复杂度想问题。这一步显然只能在O(n)情况下解决，O(nlgn)不太可能了。所以肯定要第一次循环中提前准备下，然后第二次循环中判断。

那第一存什么呢？因为我们这里关注的是出现次数，那就用Map存储每个质因数的出现次数。然后在第二次循环中，用一个新的map，表示当前循环位置质因数的出现次数，与预先存储的map对比，如果有重复质因数出现，那么两个size相加就会大于一开始整个数组的size。

出现次数考虑整体，用map。

教训：

• 复杂度解题。看到数组大小10^4，每个数10^6，可以明白10^(4+6/2)下不会TLE(理论下O(10^7)或者严格O(10^8)一下都可以)，所以可以用质因数分解。然后我试着用O(10^7)存储空间，但MLE了，所以感觉空间复杂度最好不超过O(10^6)，这也是一些图的题目的二维数组极限大小
• 不要轻信copilot，还是要检查下它生成的代码，质因数代码生成的时候while写成if了。。

class Solution {
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> primes = new HashMap<>();
        for (int num : nums) {
            // split nums[i] into prime factors
            int j = 2;
            while (j * j <= num) {
                while (num % j == 0) {
                    primes.put(j, primes.getOrDefault(j, 0) + 1);
                    num /= j;
                }
                ++j;
            }
            if (num > 1) {
                primes.put(num, primes.getOrDefault(num, 0) + 1);
            }
        }
        int total = primes.size();
        Map<Integer, Integer> factors = new HashMap<>();
        for (int i = 0; i < nums.length - 1; ++i) {
            // split nums[i] into prime factors
            int j = 2;
            int num = nums[i];
            while (j * j <= num) {
                while (num % j == 0) {
                    factors.put(j, factors.getOrDefault(j, 0) + 1);
                    primes.put(j, primes.getOrDefault(j, 0) - 1);
                    if (primes.get(j) == 0) {
                        primes.remove(j);
                    }
                    num /= j;
                }
                ++j;
            }
            if (num > 1) {
                factors.put(num, factors.getOrDefault(num, 0) + 1);
                primes.put(num, primes.getOrDefault(num, 0) - 1);
                if (primes.get(num) == 0) {
                    primes.remove(num);
                }
            }
            if (factors.size() + primes.size() == total) {
                return i;
            }
        }
        return -1;
    }
}

---

• 2584. Split the Array to Make Coprime Products