给你一个整数 num,请你找出同时满足下面全部要求的两个整数: 两数乘积等于 num + 1 或 num + 2 以绝对差进行度量,两数大小最接近 你可以按任意顺序返回这两个整数。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/closest-divisors 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
其实就是找num + 1 和 num + 2,所有一对一对的因子中,相距最小的。
对于num + 1 和 num + 2中所有成对的因子,每一对都必定有一个小于或者等于(num+2)1/2 的
简单证明:假设有一对都大于(num+2)1/2 ,它们俩的乘积一定大于(num+2)1/2 *(num+2)1/2=num+2;矛盾
现在,我们有了,没一对因子中,较小的那一个的上界。
而,较小因子越大,较大因子也越小,这样才能使得两个因子距离最小
这下思路就清晰了!从(num+2)1/2 往小遍历,只要找到可以整除num + 1 或 num + 2的,就一定是答案的一部分!剩下一个因子除一下就好了;
class Solution {
public int[] closestDivisors(int num
) {
int[] re
=new int[2];
int ans
=(int)Math
.sqrt(num
+2);
while(true){
if((num
+1)%ans
==0||(num
+2)%ans
==0){
break;
}
ans
--;
}
if((num
+1)%ans
==0){
re
[0]=(num
+1)/ans
;
re
[1]=ans
;
}else{
re
[0]=(num
+2)/ans
;
re
[1]=ans
;
}
return re
;
}
}
转载请注明原文地址:https://tech.qufami.com/read-19910.html