本文涉及内容

质因数分解 差分数组

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 <= 10⁴
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()]–;
第四步：如果${\sum }_{x:0}^{i}vDiff[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;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31

测试用例

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);
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。