本文共 1642 字，大约阅读时间需要 5 分钟。

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

• 两数乘积等于 num + 1 或 num + 2
• 以绝对差进行度量，两数大小最接近

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

示例 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]

提示：

• 1 <= num <= 10^9

解题思路

首先不难想到暴力解法的思路，也就是遍历[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, itertoolsclass 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

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

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104490629 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！