class Solution {
public:
vector<int> closestDivisors(int num) {
}
};
1362. 最接近的因数
给你一个整数 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原站题解
python3 解法, 执行用时: 148 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-11 12:58:23
class Solution:
def closestDivisors(self, num: int) -> List[int]:
# a, b => a * b == num + 1 or a * b == num + 2
def getFactors(num):
sqrt = int(math.sqrt(num) + 1)
for i in range(sqrt, 0, -1):
if num % i == 0:
return (i, num // i)
a1, b1 = getFactors(num + 1)
a2, b2 = getFactors(num + 2)
if abs(a1 - b1) < abs(a2 - b2):
return [a1, b1]
else:
return [a2, b2]
java 解法, 执行用时: 2 ms, 内存消耗: 39 MB, 提交时间: 2022-12-11 12:57:59
class Solution {
public int[] closestDivisors(int num) {
int divisor = num == 1 ? num + 1 : num + 2;
int i = (int) Math.sqrt(divisor);
while (divisor % i > 1) {
i--;
}
return new int[]{i, divisor / i};
}
}
java 解法, 执行用时: 5 ms, 内存消耗: 39.2 MB, 提交时间: 2022-12-11 12:57:42
class Solution {
public int[] closestDivisors(int num) {
int sum1 = num + 1;
int sum2 = num + 2;
int[] res1 = getDivisors(sum1);
int[] res2 = getDivisors(sum2);
return Math.abs(res1[0] - res1[1]) < Math.abs(res2[0] - res2[1]) ? res1:res2;
}
private int[] getDivisors(int sum){
int num1 = (int) Math.sqrt(sum);
while (true){
if (sum % num1 == 0){
int num2 = sum / num1;
return new int[]{num1,num2};
}else {
num1--;
}
}
}
}
python3 解法, 执行用时: 152 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-11 12:57:18
class Solution:
def divide(self, n):
for i in range(int(math.sqrt(n)), 0, -1):
if n % i == 0:
return [i, n // i]
def closestDivisors(self, num: int) -> List[int]:
ans = [0, int(1e9)]
for i in range(num + 1, num + 3):
cur = self.divide(i)
if abs(cur[0] - cur[1]) < abs(ans[0] - ans[1]):
ans = cur
return ans