本文涉及内容
质因数分解 差分数组
LeetCode2584. 分割数组使乘积互质
给你一个长度为 n 的整数数组 nums ，下标从 0 开始。
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。
例如，如果 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 <= 104
1 <= nums[i] <= 10^6
题解
如果多个数包括质因数x，则这些数不能分开。假定这些数的最小下标和最大下标，分别为i1,i2。
则i不能为[i1,i2)，注意左闭右开空间。
刚好用差分数组实现。
第一步：获取1000以内的质数。
第二步：分解nums[i]的质因数，并将下标放到indexs中，indexs[iPri]记录质因数包括iPri的下标。
第三步：枚举各数，如果是质数，且indexs[i]包括两个下标。
vDiff[indexs[i].front()]++;
vDiff[indexs[i].back()]–;
第四步：如果∑ x : 0 i v D i f f [ x ] \sum_{x:0}^ivDiff[x]∑x:0ivDiff[x] 为0，返回i。注意 ：i的取值范围[0,nums.size()-2]
代码
核心代码
class Solution { public: int findValidSplit(vector<int>& nums) { auto vPrime = CreatePrime(1'000); const int iMax = *std::max_element(nums.begin(),nums.end()); vector<vector<int>> indexs(iMax+1); for (int i = 0; i < nums.size(); i++) { int tmp = nums[i]; for (auto& iPri : vPrime) { if (iPri * iPri > tmp) { break; } if (0 == tmp % iPri) { indexs[iPri].emplace_back(i); } while ((0 == tmp % iPri)) { tmp /= iPri; } } if( tmp > 1){ indexs[tmp].emplace_back(i); } } vector<int> vDiff(nums.size() ); for (int i = 0; i <= iMax; i++) { if (indexs[i].size() < 2) { continue; } vDiff[indexs[i].front()]++; vDiff[indexs[i].back()]--; } int iSum = 0; for (int i = 0; i +1< nums.size(); i++) { iSum += vDiff[i]; if (0 == iSum) { return i; } } return -1; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; { Solution sln; nums = { 4, 7, 8, 15, 3, 5 }; auto res = sln.findValidSplit(nums); Assert(2, res); } { Solution sln; nums = { 4,7,15,8,3,5 }; auto res = sln.findValidSplit(nums); Assert(-1, res); } }
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
