class Solution {
public:
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
}
};
2344. 使数组可以被整除的最少删除次数
给你两个正整数数组 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[i], numsDivide[i] <= 109原站题解
golang 解法, 执行用时: 180 ms, 内存消耗: 9.8 MB, 提交时间: 2023-10-10 16:09:03
func minOperations(nums, numsDivide []int) int {
g := 0
for _, x := range numsDivide {
g = gcd(g, x)
}
sort.Ints(nums)
for i, x := range nums {
if g%x == 0 {
return i
}
}
return -1
}
// 不排序，两次遍历
func minOperations2(nums, numsDivide []int) (ans int) {
g := 0
for _, x := range numsDivide {
g = gcd(g, x)
}
min := math.MaxInt32
for _, x := range nums {
if g%x == 0 && x < min {
min = x
}
}
if min == math.MaxInt32 {
return -1
}
for _, x := range nums {
if x < min {
ans++
}
}
return
}
func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }
cpp 解法, 执行用时: 116 ms, 内存消耗: 86.4 MB, 提交时间: 2023-10-10 16:07:58
class Solution {
public:
// 不排序，两次遍历
int minOperations(vector<int> &nums, vector<int> &numsDivide) {
int g = 0;
for (int x : numsDivide) g = gcd(g, x);
int mn = INT_MAX;
for (int x : nums) if (g % x == 0) mn = min(mn, x);
if (mn == INT_MAX) return -1;
int ans = 0;
for (int x : nums) if (x < mn) ++ans;
return ans;
}
// 排序，贪心
int minOperations2(vector<int> &nums, vector<int> &numsDivide) {
int g = 0;
for (int x : numsDivide) g = gcd(g, x);
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) if (g % nums[i] == 0) return i;
return -1;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 54.9 MB, 提交时间: 2023-10-10 16:07:08
class Solution {
// 排序，贪心
public int minOperations(int[] nums, int[] numsDivide) {
var g = 0;
for (var x : numsDivide) g = gcd(g, x);
Arrays.sort(nums);
for (var i = 0; i < nums.length; i++) if (g % nums[i] == 0) return i;
return -1;
}
// 不排序，两次遍历
public int minOperations2(int[] nums, int[] numsDivide) {
var g = 0;
for (var x : numsDivide) g = gcd(g, x);
var min = Integer.MAX_VALUE;
for (var num : nums) if (g % num == 0) min = Math.min(min, num);
if (min == Integer.MAX_VALUE) return -1;
var ans = 0;
for (var x : nums) if (x < min) ++ans;
return ans;
}
int gcd(int a, int b) {
return a == 0 ? b : gcd(b % a, a);
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 27.4 MB, 提交时间: 2023-10-10 16:05:54
class Solution:
def minOperations1(self, nums: List[int], numsDivide: List[int]) -> int:
g = gcd(*numsDivide)
nums.sort()
return next((i for i, x in enumerate(nums) if g % x == 0), -1)
# 不排序，两次遍历
def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
g = gcd(*numsDivide)
mn = min((x for x in nums if g % x == 0), default=0)
return sum(x < mn for x in nums) if mn else -1