Leetcode.2344 使数组可以被整除的最少删除次数

题目链接

Leetcode.2344 使数组可以被整除的最少删除次数 Rating ： 1641

题目描述

给你两个正整数数组 $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<=1051 <= nums.length, numsDivide.length <= 10^51<=nums.length,numsDivide.length<=105
• 1<=nums[i],numsDivide[i]<=1091 <= nums[i], numsDivide[i] <= 10^91<=nums[i],numsDivide[i]<=109

解法：数论

如果说一个数 $x$ ，他能给整除 $numsDivide$ 中的所有元素，那么这个 $x$ 一定等于 $numsDivide$ 中所有元素的最大公约数 $g$ 或者是 $x$ 和 $g$ 的最小公倍数也是 $g$，即 $lcm(x,g)=g$。

然后将 $nums$ 从小到大排序，找到第一个 $lcm(nums[i],g)=g$ 的 $i$，$i$ 前面的都是要删除的元素，要删除 $i$ 个元素。否则没找到的话，就返回 $-1$。

时间复杂度： $O(nlogn)$

C++代码：

class Solution {
public:int minOperations(vector<int>& nums, vector<int>& numsDivide) {int g = 0;for(auto x:numsDivide) g = gcd(x,g);sort(nums.begin(),nums.end());int n = nums.size();int ans = -1;for(int i = 0;i < n;i++){if(lcm<int>(g,nums[i]) == g) {ans = i;break;}//nums[i] > g 这之后 nums[i] 和 g 的最小公倍数一定会大于 g ，所以可以直接退出循环了else if(nums[i] > g) break;}return ans;}
};

EL-ADMIN 在线文档