题目

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

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If this is not possible, return -1.

Note that an integer x divides y if y % x == 0.

Example 1:

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: 
The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of numsDivide.
We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums = [3,4,3].
The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide.
It can be shown that 2 is the minimum number of deletions needed.

Example 2:

Input: nums = [4,3,6], numsDivide = [8,2,6,10]
Output: -1
Explanation: 
We want the smallest element in nums to divide all the elements of numsDivide.
There is no way to delete elements from nums to allow this.

Constraints:

• 1 <= nums.length, numsDivide.length <= 105
• 1 <= nums[i], numsDivide[i] <= 109

思路

题目大意，给定nums和numsDivide两个数组，在nums中删除数字，使得nums中最小数字可以整除numsDivide中所有数字。

思路很简单，求numsDivide的最大公约数（gcd），在把nums从小往大删，直到gcd（numsDivide）% min（nums）==0为止。

非常水的一道hard了，个人感觉medium比较合适。

代码

几个可以优化的点

1.gcd如何求？可以自己实现辗转相除法，也可以使用系统版本。亲测效率差不多。

2.如何删除nums最小数字？可以使用堆排序（heapq），也可以排序。亲测直接排序要快上很多。

import fractions
class Solution(object):
    def minOperations(self, nums, numsDivide):
        """
        :type nums: List[int]
        :type numsDivide: List[int]
        :rtype: int
        """
        nums.sort()
        if nums[0] == 1:
            return 0
        g = numsDivide[0]
        for n in numsDivide:
            g = fractions.gcd(g, n)
            if g == 1:
                break
                
        for i in range(len(nums)):
            if g % nums[i] == 0:
                return i
        return -1

AC，收工。

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/07/21/leetcode-2344-minimum-deletions-to-make-array-divisible/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！