题解的总体思路是首先计算 num+1 和 num+2 的因数,并找到每个数的两个因数,使得这两个因数的乘积正好等于 num+1 或 num+2。为了找到最接近的因数,题解采用了从最大可能的因数(即 sqrt(n))开始递减检查的方式,直到找到第一个因数。这样可以确保找到的因数对差值最小,因为开始检查的是最接近 sqrt(n) 的因数。计算出 num+1 和 num+2 的因数后,比较这两对因数的差的绝对值,返回差值较小的那对因数。
时间复杂度: O(sqrt(num))
空间复杂度: O(1)
import math
class Solution:
def closestDivisors(self, num: int) -> List[int]:
def get_factors(n):
# 找到最接近的两个因数
f = int(math.sqrt(n))
for i in range(f, 0, -1):
if n % i == 0:
return [i, n // i]
# 计算 num+1 的因数
ff1 = get_factors(num + 1)
# 计算 num+1 因数的差的绝对值
dis1 = abs(ff1[0] - ff1[1])
# 计算 num+2 的因数
ff2 = get_factors(num + 2)
# 计算 num+2 因数的差的绝对值
dis2 = abs(ff2[0] - ff2[1])
# 返回差值较小的因数对
return ff1 if dis1 < dis2 else ff2