英文原文
Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
Example 1:
Input: num = 8 Output: [3,3] Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
Example 2:
Input: num = 123 Output: [5,25]
Example 3:
Input: num = 999 Output: [40,25]
Constraints:
1 <= num <= 10^9
中文题目
给你一个整数 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
通过代码
高赞题解
解题思路
均值不等式可知 a+b>=2*sqrt(a*b)，两个数和固定的情况下，两数越接近，他们的乘积越大。
所以，直接先开根号，然后递减遍历，当数字可以被sum整除，就可以直接返回了，不需要继续遍历，这个时候得到的乘积，一定是最大的。
最后只要比较num+1得到的因子和num+2得到的因子，差的绝对值较小的那个即可
代码
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--;
}
}
}
}统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 5697 | 10752 | 53.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
