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

标签: 数组 数学 数论 排序 堆（优先队列）

难度: 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 中所有元素。
我们从 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

Submission

运行时间: 56 ms

内存: 27.0 MB

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        x = gcd(*numsDivide)
        y = min((v for v in nums if x % v == 0), default=0)
        return sum(v < y for v in nums) if y else -1

Explain

本题解首先通过计算 numsDivide 中所有元素的最大公约数（GCD）x，从而确定需要的整除因子。然后在 nums 中查找可以被 x 整除的最小元素 y。如果找到这样的 y，则计算必须删除 nums 中所有小于 y 的元素才能使 y 成为 nums 中的最小元素。如果没有找到可以整除 x 的元素，则返回 -1。

时间复杂度: O(n + k)

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        from math import gcd
        # 计算 numsDivide 中所有元素的最大公约数 x
        x = gcd(*numsDivide)
        # 在 nums 中寻找能被 x 整除的最小元素 y
        y = min((v for v in nums if x % v == 0), default=0)
        # 如果没有找到符合条件的 y，则返回 -1
        if y == 0:
            return -1
        # 计算 nums 中小于 y 的元素数量，即需要删除的元素数量
        return sum(v < y for v in nums)

Explore

计算 `numsDivide` 中所有元素的最大公约数（GCD）是为了找出一个数字，该数字能被 `numsDivide` 中所有元素整除。这个步骤关键在于确定一个共同的整除因子，确保任何被这个 GCD 整除的数也必然能整除 `numsDivide` 中的每个元素。这样，我们只需要关注 `nums` 中能被这个 GCD 整除的数，从而简化问题范围和处理逻辑。

选择 `nums` 中可以被 GCD 整除的最小元素作为目标的原因是为了最小化需要删除的数字数量。如果我们以最小的符合条件的元素为基准，那么所有小于此元素的数字都需要被删除，以确保所有更大的、符合条件的数字仍然保留在数组中。这样可以确保删除操作尽可能少，达到题目要求的最少删除次数。

如果 `nums` 中不存在可以被 GCD 整除的元素，并直接返回 `-1`，这通常意味着 `nums` 中的元素与 `numsDivide` 的 GCD 不兼容，可能是因为 GCD 太大，或者 `nums` 中的元素范围不够广泛，无法包含任何可以被 GCD 整除的值。这种情况下，`nums` 数组无法调整来满足 `numsDivide` 中所有元素的整除要求。

`default=0` 在这里的作用是提供一个默认值，用于处理当 `nums` 中没有任何元素能被 GCD 整除的情况。在这种情况下，`min` 函数没有元素可用来比较，如果没有 `default`，则会抛出异常。通过设置 `default=0`，我们可以安全地检测到没有符合条件的元素，并据此返回 `-1`，表示无法通过删除使 `nums` 满足条件。