class Solution {
public:
int kthFactor(int n, int k) {
}
};
1492. n 的第 k 个因子
给你两个正整数 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) 的算法来解决此问题吗？
原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2022-11-29 12:04:39
class Solution {
public int kthFactor(int n, int k) {
int count = 0, factor;
for (factor = 1; factor * factor <= n; ++factor) {
if (n % factor == 0) {
++count;
if (count == k) {
return factor;
}
}
}
--factor;
if (factor * factor == n) {
--factor;
}
for (; factor > 0; --factor) {
if (n % factor == 0) {
++count;
if (count == k) {
return n / factor;
}
}
}
return -1;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-29 12:04:21
class Solution:
def kthFactor(self, n: int, k: int) -> int:
count = 0
factor = 1
while factor * factor <= n:
if n % factor == 0:
count += 1
if count == k:
return factor
factor += 1
factor -= 1
if factor * factor == n:
factor -= 1
while factor > 0:
if n % factor == 0:
count += 1
if count == k:
return n // factor
factor -= 1
return -1
java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2022-11-29 12:02:41
class Solution {
public int kthFactor(int n, int k) {
int count = 0;
for (int factor = 1; factor <= n; ++factor) {
if (n % factor == 0) {
++count;
if (count == k) {
return factor;
}
}
}
return -1;
}
}
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-29 12:02:17
class Solution:
def kthFactor(self, n: int, k: int) -> int:
count = 0
for factor in range(1, n+1):
if n % factor == 0:
count += 1
if count == k:
return factor
return -1