本文涉及知识点
最大公约数 排序
LeetCode2344. 使数组可以被整除的最少删除次数
给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。
请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。
如果 y % x == 0 ，那么我们说整数 x 整除 y 。
示例 1：
输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。
示例 2：
输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。
提示：
1 <= nums.length, numsDivide.length <= 105
1 <= nums[i], numsDivide[i] <= 109
最大公约数
numsDivide 所有元素都整除x，说明numsDivide 所有元素都是x的倍数，即gcd(numsDivide )也是x的倍数。即 gcd(gcd(numsDivide ),x) == x。
先将nums排序，直到找到符合条件的数，返回次数的下标。如果没找到返回-1。
代码
核心代码
class Solution { public: int minOperations(vector<int>& nums, vector<int>& numsDivide) { int iGCD = numsDivide.front(); for (const auto& n : numsDivide) { iGCD = gcd(iGCD, n); } sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] == gcd(iGCD, nums[i])) { 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, numsDivide; { Solution sln; nums = { 2, 3, 2, 4, 3 }, numsDivide = { 9, 6, 9, 3, 15 }; auto res = sln.minOperations(nums, numsDivide); Assert(2, res); } { Solution sln; nums = { 4, 3, 6 }, numsDivide = { 8, 2, 6, 10 }; auto res = sln.minOperations(nums, numsDivide); Assert(-1, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
