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 <= 105
• 1 <= nums[i], numsDivide[i] <= 109

本题 视频讲解 已出炉，欢迎点赞三连~

---

提示 1

元素 x 若能整除 numsDivide 的所有元素，等价于 x 是所有 numsDivide}[i] 的因子，这也等价于 x 是 numsDivide 所有元素的最大公因数 g 的因子。

提示 2

由于要求用 nums 的最小元素去整除 g，不妨将 nums 排序后，从小到大找到第一个能整除 g 的元素 x，所有小于 x 的元素都需要删除。

[sol1-Python3]

class Solution:
    def minOperations(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)

[sol1-Java]

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

    int gcd(int a, int b) {
        return a == 0 ? b : gcd(b % a, a);
    }
}

[sol1-C++]

class Solution {
public:
    int minOperations(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;
    }
};

[sol1-Go]

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 gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

也可以不用排序，通过两次遍历得到答案。

[sol2-Python3]

class Solution:
    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

[sol2-Java]

class Solution {
    public int minOperations(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);
    }
}

[sol2-C++]

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

[sol2-Go]

func minOperations(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
}

复杂度分析

• 时间复杂度：O(m+\log U + n)，其中 m 为数组 numsDivide 的长度，U=\max(\textit{numsDivide})，n 为数组 nums 的长度。注意到求最大公因数 g 的过程（设初始 g=U），要么使 g 不变，要么使 g 至少减半，而 g 至多减半 O(\log U) 次，因此求最大公因数的迭代次数为 O(m+\log U) 次。总的时间复杂度为 O(m+\log U + n)。
• 空间复杂度：O(1)。仅需要几个额外的变量。