Medium

题目描述

给定一个整数 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

提示：

  • 找到 n+1 和 n+2 的因数
  • 要找到一个数的因数，只需要迭代到该数的平方根

解题思路

这道题要求找到两个因数，使得它们的乘积为 num + 1 或 num + 2，且两个因数之间的差值最小。

核心思路： 要使两个因数的差值最小，这两个因数应该尽可能接近该数的平方根。因此我们从平方根开始向下搜索，找到的第一对因数就是差值最小的。

算法步骤：

  1. 对于每个候选值（num + 1 和 num + 2），从其平方根开始向下遍历
  2. 找到第一个能整除该数的因子 i，那么另一个因子就是 target / i
  3. 比较两个候选值得到的因数对，返回差值更小的那一对

优化点：

  • 从平方根开始向下搜索，第一个找到的因数对就是最优解
  • 只需要检查 num + 1 和 num + 2 两个候选值
  • 由于我们要的是差值最小的因数对，实际上可以先检查 num + 2，如果没找到完全平方数的情况，再检查 num + 1

时间复杂度：O(√n)，空间复杂度：O(1)

代码实现

class Solution {
public:
    vector<int> closestDivisors(int num) {
        // 检查 num + 2，然后检查 num + 1
        for (int target : {num + 2, num + 1}) {
            int root = sqrt(target);
            for (int i = root; i >= 1; i--) {
                if (target % i == 0) {
                    return {i, target / i};
                }
            }
        }
        return {}; // 不会到达这里
    }
};

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        # 检查 num + 2，然后检查 num + 1
        for target in [num + 2, num + 1]:
            root = int(target ** 0.5)
            for i in range(root, 0, -1):
                if target % i == 0:
                    return [i, target // i]
        return []  # 不会到达这里

public class Solution {
    public int[] ClosestDivisors(int num) {
        // 检查 num + 2，然后检查 num + 1
        foreach (int target in new int[] {num + 2, num + 1}) {
            int root = (int)Math.Sqrt(target);
            for (int i = root; i >= 1; i--) {
                if (target % i == 0) {
                    return new int[] {i, target / i};
                }
            }
        }
        return new int[0]; // 不会到达这里
    }
}

var closestDivisors = function(num) {
    const findClosestDivisors = (n) => {
        for (let i = Math.floor(Math.sqrt(n)); i >= 1; i--) {
            if (n % i === 0) {
                return [i, n / i];
            }
        }
    };
    
    const divisors1 = findClosestDivisors(num + 1);
    const divisors2 = findClosestDivisors(num + 2);
    
    const diff1 = Math.abs(divisors1[1] - divisors1[0]);
    const diff2 = Math.abs(divisors2[1] - divisors2[0]);
    
    return diff1 <= diff2 ? divisors1 : divisors2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(√n)需要遍历到目标数的平方根
空间复杂度O(1)只使用常量额外空间

相关题目