标签: 数学
难度: Medium
给你一个整数 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运行时间: 66 ms
内存: 16.0 MB
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]
ff1=get_factors(num+1)
dis1=abs(ff1[0]-ff1[1])
ff2=get_factors(num+2)
dis2=abs(ff2[0]-ff2[1])
return ff1 if dis1<dis2 else ff2
题解的总体思路是首先计算 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
从整数的平方根开始递减搜索因数是为了尽快找到两个相差较小的因数。当从平方根开始向下搜索时，找到的第一组因数通常是两者相差最小的，因为这是从中间向两端搜索。如果从1开始递增，则首先会找到较小的因数，其配对的另一个因数会比较大，这样得到的两个因数之间的差值通常会更大。
因为如果n可以被i整除，说明i是n的一个因数，而n/i也一定是n的因数。这样，i和n/i就构成了n的一对因数。在我们从平方根开始递减搜索的过程中，找到的第一对因数就是两个因数相差最小的，因此可以直接返回这对因数作为答案。
算法首先计算出num+1和num+2的因数对，并分别计算这两对因数的差的绝对值。通过比较这两个差值，可以确定哪一对因数的差值更小。返回差值更小的因数对可以保证返回的是两个数相差最小的因数对，从而满足题目要求。