题目大意：
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 。
示例 4：
输入：n = 1, k = 1 输出：1 解释：因子列表包括 [1] ，第 1 个因子为 1 。
示例 5：
输入：n = 1000, k = 3 输出：4 解释：因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。
提示：
1 <= k <= n <= 1000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1492
解题思路分析：
这道题的数据规模并不大，因此我们可以暴力求解n的第k个因子。我们从1循环至n，如果当前数可以被n整除，那么它即是n的一个因子，并将k减一。当k变为0时，当前数字即是n的第k个因子。如果循环结束后k仍大于0，返回-1。这种解法的时间复杂度为O(n)，空间复杂度为O(1)。
引申思考一下，如果本题n的范围是1亿的话，那么我们最坏需要循环1亿次才能得出结果，显然O(n)的时间复杂度难以胜任。此时我们可以以牺牲空间的方式来节约时间。解题时我们只需要循环至sqrt(n)即可，如果当前数字i可以被n整除，那么n/i这个数字同样可以被n整除，换句话说，每当找到n的一个因子时，实际上我们同时找到了它的一对因子，唯一的例外是i等于i/n。我们将所有找到的因子保存至List集合，然后再按照升序排序。如果List的元素个数小于k时，返回-1，反之返回list中第k个元素即可。这样时间复杂度就降至O(sqrt(n))，但空间复杂度会变为O(n)，n为所有因子个数。
实现代码1：暴力解法
public int kthFactor(int n, int k) {
for(int i=1;i<=n;i++){
if(n%i==0) k--;
if(k==0) return i;
}
return -1;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for The kth Factor of n.
Memory Usage: 36.5 MB, less than 100.00% of Java online submissions for The kth Factor of n.
实现代码2：集合加排序
public int kthFactor(int n, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>(); // 升序保存每一个因子
for(int i=1;i*i<=n;i++){ // 从1循环至根号n
if(n%i ==0){ // 如果当前数字可以被n整除
q.offer(i); // 当前数字是一个因子，加入到queue
// n/i也一定是一个因子，
// 如果 i不等于n/i，将n/i也加入到queue
if(i*i!=n) q.offer(n/i);
}
}
while(q.size()>0){ // 从queue中取出第k个元素即是返回结果
int num=q.poll();
if(--k==0) return num;
}
return -1;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 80.18% of Java online submissions for The kth Factor of n.
Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for The kth Factor of n.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1492-the-kth-factor-of-n-解题思路分析/