最接近的因数
难度:
标签:
题目描述
Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
Example 1:
Input: num = 8 Output: [3,3] Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
Example 2:
Input: num = 123 Output: [5,25]
Example 3:
Input: num = 999 Output: [40,25]
Constraints:
1 <= num <= 10^9
代码结果
运行时间: 66 ms, 内存: 16.0 MB
/*
* Approach:
* Using Java Streams to find two integers whose product is equal to either num + 1 or num + 2, and whose absolute difference is minimal.
*/
import java.util.stream.IntStream;
public class Solution {
public int[] closestDivisors(int num) {
int[] result1 = findClosestDivisors(num + 1);
int[] result2 = findClosestDivisors(num + 2);
return (Math.abs(result1[0] - result1[1]) < Math.abs(result2[0] - result2[1])) ? result1 : result2;
}
private int[] findClosestDivisors(int num) {
return IntStream.rangeClosed(1, (int) Math.sqrt(num))
.filter(i -> num % i == 0)
.mapToObj(i -> new int[]{i, num / i})
.min((a, b) -> Integer.compare(Math.abs(a[0] - a[1]), Math.abs(b[0] - b[1])))
.orElse(new int[]{1, num}); // Shouldn't reach here for valid inputs
}
}解释
方法:
题解的总体思路是首先计算 num+1 和 num+2 的因数，并找到每个数的两个因数，使得这两个因数的乘积正好等于 num+1 或 num+2。为了找到最接近的因数，题解采用了从最大可能的因数（即 sqrt(n)）开始递减检查的方式，直到找到第一个因数。这样可以确保找到的因数对差值最小，因为开始检查的是最接近 sqrt(n) 的因数。计算出 num+1 和 num+2 的因数后，比较这两对因数的差的绝对值，返回差值较小的那对因数。
时间复杂度:
O(sqrt(num))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择从整数的平方根开始递减搜索因数，而不是从1开始递增搜索？
▷🦆
在寻找因数的过程中，如果直接找到一个因数，为什么可以直接返回该因数和n除以该因数得到的结果作为答案？
▷🦆
如何保证在比较num+1和num+2的因数对时，返回的确实是差值绝对最小的那一对？
▷