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 the kth 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?
代码结果
运行时间: 22 ms, 内存: 0.0 MB
/*
* 思路：
* 1. 使用IntStream从1到n遍历所有整数。
* 2. 过滤出所有的因子，并将其收集到列表中。
* 3. 判断列表的大小是否大于等于k，如果是，返回第k个因子，否则返回-1。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int kthFactor(int n, int k) {
List<Integer> factors = IntStream.rangeClosed(1, n)
.filter(i -> n % i == 0)
.boxed()
.collect(Collectors.toList());
return factors.size() >= k ? factors.get(k - 1) : -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)
代码细节讲解
🦆
在算法中，为何选择直接遍历从 1 到 n 来查找因子，而不使用其他可能更高效的方法（如只遍历到 sqrt(n)）？
▷🦆
在代码中，如果找到一个因子 i ，是否还可以立即确定 n/i 也是一个因子，从而可能减少遍历的次数？
▷🦆
算法在碰到顺序的第 k 个因子时直接返回，但如果 k 大于 n 的因子总数，会返回 -1。这里是否进行了所有必要的检查，以确保算法的正确性和效率？
▷