Hard

题目描述

给你两个正整数数组 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 中所有元素。
我们删除 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 中所有元素。
无法通过删除 nums 中元素来实现这一点。

约束条件：

  • 1 <= nums.length, numsDivide.length <= 10^5
  • 1 <= nums[i], numsDivide[i] <= 10^9

解题思路

这道题的核心思路是找到一个能整除 numsDivide 所有元素的最小值。

关键观察：

  1. 如果一个数能整除数组中的所有元素，那么它一定能整除这些元素的最大公约数(GCD)
  2. 反之，如果一个数能整除这些元素的GCD，它就能整除数组中的所有元素
  3. 因此，我们要找的目标数必须是 numsDivide 所有元素的GCD的因子

算法步骤：

  1. 计算 numsDivide 数组的GCD
  2. 对 nums 数组排序
  3. 从最小元素开始，找到第一个能整除GCD的元素
  4. 返回需要删除的元素个数

时间复杂度优化：

  • 可以用计数的方式避免多次遍历相同元素
  • 排序后按值递增顺序检查，找到第一个可行解即为最优解

这种方法的优势是利用了GCD的数学性质，将问题转化为寻找GCD的最小因子，大大简化了解题复杂度。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        // 计算numsDivide的GCD
        int g = numsDivide[0];
        for (int i = 1; i < numsDivide.size(); i++) {
            g = gcd(g, numsDivide[i]);
        }
        
        // 排序nums
        sort(nums.begin(), nums.end());
        
        // 找到第一个能整除GCD的元素
        for (int i = 0; i < nums.size(); i++) {
            if (g % nums[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        from math import gcd
        from functools import reduce
        
        # 计算numsDivide的GCD
        g = reduce(gcd, numsDivide)
        
        # 排序nums
        nums.sort()
        
        # 找到第一个能整除GCD的元素
        for i, num in enumerate(nums):
            if g % num == 0:
                return i
        
        return -1

public class Solution {
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
    
    public int MinOperations(int[] nums, int[] numsDivide) {
        // 计算numsDivide的GCD
        int g = numsDivide[0];
        for (int i = 1; i < numsDivide.Length; i++) {
            g = GCD(g, numsDivide[i]);
        }
        
        // 排序nums
        Array.Sort(nums);
        
        // 找到第一个能整除GCD的元素
        for (int i = 0; i < nums.Length; i++) {
            if (g % nums[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
}

var minOperations = function(nums, numsDivide) {
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    let targetGcd = numsDivide[0];
    for (let i = 1; i < numsDivide.length; i++) {
        targetGcd = gcd(targetGcd, numsDivide[i]);
    }
    
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length; i++) {
        if (targetGcd % nums[i] === 0) {
            return i;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n + m log(max(numsDivide)))
空间复杂度O(1)

说明：

  • 时间复杂度：排序 nums 需要 O(n log n)，计算GCD需要 O(m log(max(numsDivide)))，其中 n 是 nums 长度，m 是 numsDivide 长度
  • 空间复杂度：只使用常数额外空间（不考虑排序的空间开销）

相关题目