题目大意：
最接近的因数
给你一个整数 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1362
解题思路分析：
本题需要使用到贪心算法，试想，如果a乘以b等于c，要想a和b的差值最小，那么最好的情况即是a等于b，因此我们可以先求出c的平方根sqrt（整数解），如果c与sqrt的余数为0，说明我们可以使用两个sqrt相乘得到c，这肯定是最优解。如果余数不为0,我们尝试将sqrt减一，然后继续求c与sqrt的余数，直到余数为0时， sqrt 和 c除以sqrt即是c的两个最接近因数。
我们分别求出num+1和num+2的两个最接近因数，因数差最小的两个因数即是答案。
实现代码：
public int[] closestDivisors(int num) {
// num+1的两个因数
int[] nums1=new int[2];
// num+2的两个因数
int[] nums2=new int[2];
// 求num+1的两个因数
int diff1=getDiff(num+1, nums1);
// 求num+2的两个因数
int diff2=getDiff(num+2, nums2);
// 如果diff1小于diff2，返回num+1的两个因数
if(diff1<diff2){
return new int[]{nums1[0],nums1[1]};
}else{
// 反之，返回num+2的两个因数
return new int[]{nums2[0],nums2[1]};
}
}
// 求n的两个差值最小的因数
int getDiff(int n, int[] nums){
int sqrt=(int)Math.sqrt(n);
int num1=0,num2=0;
while(sqrt>0){
if(n%sqrt==0){
num1=sqrt;
num2=n/sqrt;
break;
}
sqrt--;
}
nums[0]=num1;
nums[1]=num2;
return Math.abs(num2-num1);
}本题解法执行时间为7ms。
Runtime: 7 ms, faster than 87.44% of Java online submissions for Closest Divisors.
Memory Usage: 37 MB, less than 100.00% of Java online submissions for Closest Divisors.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1362-closest-divisors-解题思路分析/