1492. n 的第 k 个因子
1492. n 的第 k 个因子
题目
You are given two positive integers n
and k
. A factor of an integer n
is defined as an integer i
where n % i == 0
.
Consider a list of all factors of n
sorted in ascending order , return thekth
factor in this list or return -1
if n
has less than k
factors.
Example 1:
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Constraints:
1 <= k <= n <= 1000
Follow up:
Could you solve this problem in less than O(n)
complexity?
题目大意
给你两个正整数 n
和 k
。
如果正整数 i
满足 n % i == 0
,那么我们就说正整数 i
是整数 n
的因子。
考虑整数 n
的所有因子,将它们 升序排列 。请你返回第 k
个因子。如果 n
的因子数少于 k
,请你返回 -1
。
示例 1:
输入: n = 12, k = 3
输出: 3
解释: 因子列表包括 [1, 2, 3, 4, 6, 12],第 3 个因子是 3 。
示例 2:
输入: n = 7, k = 2
输出: 7
解释: 因子列表包括 [1, 7] ,第 2 个因子是 7 。
示例 3:
输入: n = 4, k = 4
输出: -1
解释: 因子列表包括 [1, 2, 4] ,只有 3 个因子,所以我们应该返回 -1 。
提示:
1 <= k <= n <= 1000
进阶:
你可以设计时间复杂度小于 O(n)
的算法来解决此问题吗?
解题思路
思路一:暴力枚举因子
- 遍历从
1
到n
的所有整数,检查哪些数可以整除n
。 - 每找到一个因子,将计数器加一。
- 如果计数器达到
k
,返回当前因子。 - 如果遍历结束后还未找到第
k
个因子,返回-1
。
复杂度分析
- 时间复杂度:
O(n)
,需要遍历从1
到n
的所有整数。适用于小规模的输入,计算简单,但效率较低。 - 空间复杂度:
O(1)
,只使用了常数空间。
思路二:优化的因子枚举
- 利用因子的对称性,如果
i
是n
的因子,那么n / i
也是。 - 我们只需要遍历
1
到sqrt(n)
的整数,并记录对应的对称因子,通过双重循环,检查前k
个因子即可。 - 如果平方根对应的因子出现两次(如
16
的因子4
),跳过重复因子。 - 减少遍历范围为
1
到sqrt(n)
,有效降低了时间复杂度。 - 分两阶段遍历分别处理小因子和大因子,避免排序。
复杂度分析
- 时间复杂度:
O(sqrt(n))
,第一阶段遍历小因子,第二阶段遍历对称因子。 - 空间复杂度:
O(1)
,不使用额外存储,仅记录计数。
代码
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var kthFactor = function (n, k) {
let count = 0;
for (let i = 1; i <= n; i++) {
// 从 1 遍历到 n
if (n % i == 0) {
// 检查是否是因子
count++;
if (count == k) {
// 找到第 k 个因子
return i;
}
}
}
return -1; // 未找到第 k 个因子
};
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var kthFactor = function (n, k) {
const num = Math.floor(Math.sqrt(n)); // 计算 n 的平方根
for (let i = 1; i <= num; i++) {
if (n % i == 0 && --k == 0) {
// 小因子阶段
return i;
}
}
for (let i = num; i > 0; --i) {
// 对称因子阶段
if (i * i == n) {
// 跳过重复因子
continue;
}
if (n % i == 0 && --k == 0) {
return n / i; // 返回对应的对称因子
}
}
return -1; // 未找到第 k 个因子
};