Leetcode 1362:最接近的因数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1362:最接近的因数(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数 num,请你找出同时满足下面全部要求的两个整数:

你可以按任意顺序返回这两个整数。

示例 1:

输入:num = 8
输出:[3,3]
解释:对于 num + 1 = 9,最接近的两个因数是 3 & 3;对于 num + 2 = 10, 最接近的两个因数是 2 & 5,因此返回 3 & 3 。

示例 2:

输入:num = 123
输出:[5,25]

示例 3:

输入:num = 999
输出:[40,25]

提示:

解题思路

首先不难想到暴力解法的思路,也就是遍历[0,sqrt(n+2)]找到离的最近的两个数即可。

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        for i in range(int((num + 2)**0.5), 0, -1):
            if (num + 1) % i == 0:
                return [i, (num + 1) // i]
            if (num + 2) % i == 0:
                return [i, (num + 2) // i]

还有一种不错的解法。首先可以将num分解质因数得到数组arr,那么问题就变成了将arr分解为乘积接近的两个部分,这是一个np问题,可以通过暴力解。

import functools, operator, itertools
class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        
        def get_factor(x):
            res, i = [1], 2
            while i * i <= x:
                while x % i == 0:
                    x //= i
                    res.append(i)
                i += 1
            if x > 1:
                res.append(x)
            return res
        
        t1, t2 = get_factor(num + 1), get_factor(num + 2)
        
        res = [0, float("inf")]
        def get_closest_divisors(arr, x):
            nonlocal res
            n = len(arr)
            for i in range(1, n//2 + 1):
                for j in itertools.combinations(arr, i):
                    t = functools.reduce(operator.mul, j)
                    if abs(t - x // t) < abs(res[0] - res[1]):
                        res = [t, x// t]
        
        get_closest_divisors(t1, num + 1)
        get_closest_divisors(t2, num + 2)
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses