1362. 最接近的因数

题目描述

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

解法

方法一：枚举

我们设计一个函数 \(f(x)\)，该函数返回乘积等于 \(x\) 的两个数，且这两个数的差的绝对值最小。我们可以从 \(\sqrt{x}\) 开始枚举 \(i\)，如果 \(x\) 能被 \(i\) 整除，那么 \(\frac{x}{i}\) 就是另一个因数，此时我们就找到了一个乘积等于 \(x\) 的两个因数，我们将其返回即可。否则我们减小 \(i\) 的值，继续枚举。

接下来，我们只需要分别计算 \(f(num + 1)\) 和 \(f(num + 2)\)，然后比较两个函数的返回值，返回差的绝对值更小的那个即可。

时间复杂度 \(O(\sqrt{num})\)，空间复杂度 \(O(1)\)。其中 \(num\) 是给定的整数。

Python3JavaC++Go

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def f(x):
            for i in range(int(sqrt(x)), 0, -1):
                if x % i == 0:
                    return [i, x // i]

        a = f(num + 1)
        b = f(num + 2)
        return a if abs(a[0] - a[1]) < abs(b[0] - b[1]) else b

class Solution {
    public int[] closestDivisors(int num) {
        int[] a = f(num + 1);
        int[] b = f(num + 2);
        return Math.abs(a[0] - a[1]) < Math.abs(b[0] - b[1]) ? a : b;
    }

    private int[] f(int x) {
        for (int i = (int) Math.sqrt(x);; --i) {
            if (x % i == 0) {
                return new int[] {i, x / i};
            }
        }
    }
}

class Solution {
public:
    vector<int> closestDivisors(int num) {
        auto f = [](int x) {
            for (int i = sqrt(x);; --i) {
                if (x % i == 0) {
                    return vector<int>{i, x / i};
                }
            }
        };
        vector<int> a = f(num + 1);
        vector<int> b = f(num + 2);
        return abs(a[0] - a[1]) < abs(b[0] - b[1]) ? a : b;
    }
};

func closestDivisors(num int) []int {
    f := func(x int) []int {
        for i := int(math.Sqrt(float64(x))); ; i-- {
            if x%i == 0 {
                return []int{i, x / i}
            }
        }
    }
    a, b := f(num+1), f(num+2)
    if abs(a[0]-a[1]) < abs(b[0]-b[1]) {
        return a
    }
    return b
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

1362. 最接近的因数

题目描述

解法

方法一：枚举

评论