难度: Medium
给你两个正整数 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) 的算法来解决此问题吗？
运行时间: 22 ms
内存: 0.0 MB
class Solution:
def kthFactor(self, n: int, k: int) -> int:
for i in range(1, n+1):# skip 0?
if n % i == 0:
k -= 1
if k == 0:
return i
return -1
此题解采用直接遍历的方法来查找第 k 个因子。算法从 1 遍历到 n，对于每一个 i，检查是否能整除 n（即 n % i == 0）。如果可以整除，说明 i 是 n 的一个因子，此时将 k 减 1。当 k 减至 0 时，说明已找到第 k 个因子，返回当前的 i 值。如果遍历结束后 k 仍然大于 0，说明因子的数量不足 k 个，返回 -1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def kthFactor(self, n: int, k: int) -> int:
# 遍历从 1 到 n 的所有数
for i in range(1, n+1):
# 检查 i 是否是 n 的一个因子
if n % i == 0:
# 若是，则减少 k 的值
k -= 1
# 如果 k 降到 0，说明找到了第 k 个因子
if k == 0:
return i
# 如果遍历完所有数后还没有找到足够的因子，返回 -1
return -1
直接遍历从 1 到 n 来查找因子是一种简单明了的方法，易于理解和实现。尽管遍历到 sqrt(n) 并检查 n/i 是否也是因子可以更高效地找到所有因子，但在寻找第 k 个具体的因子时，这种方法需要额外的逻辑来正确地维护因子的顺序，因为因子对 (i, n/i) 产生的两个因子在顺序上可能不连续。此外，遍历到 n 保证了因子检查的顺序性，直接符合查找第 k 个因子的需求。
是的，如果在遍历中发现 i 是 n 的因子，可以确定 n/i 也是 n 的因子。但在查找第 k 个因子时，直接使用这种方法可能会引入顺序处理的复杂性，因为你需要同时跟踪从小到大和从大到小的因子。例如，如果 n = 36，i = 6，则 n/i = 6，这在因子序列中只应计数一次。如果 n = 28，i = 4，则 n/i = 7，这两个因子在顺序上是连续的，但这种情况并不总是成立。因此，这种优化虽然可以减少遍历次数，但需要小心处理因子的顺序和重复计数问题。
算法通过遍历每个数字并检查是否为 n 的因子，确保了正确性。如果 k 递减到 0，则返回当前的因子；如果遍历结束后 k 仍大于 0，返回 -1 表示因子数量不足 k 个。此方法确保了算法的正确性。然而，关于效率，虽然遍历到 n 是简单直接的，但它不是最优的，特别是对于大的 n 值。遍历到 sqrt(n) 并适当处理因子的顺序计数可能更加高效，尤其是当 k 较小时。