LEETCODE 1362. Closest Divisors 解题思路分析

题目大意:

最接近的因数

给你一个整数 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。