1.题目基本信息
1.1.题目描述
给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0 ,那么我们就说正整数 i 是整数 n 的因子。
考虑整数 n 的所有因子,将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ,请你返回 -1 。
1.2.题目地址
https://leetcode.cn/problems/the-kth-factor-of-n/description
2.解题方法
2.1.解题思路
优先队列(堆)+求正整数的因数
2.2.解题步骤
第一步,遍历,获取所有的因数并压入heap堆中
第二步,遍历k次,从小到大从heap堆中弹出因数。如果中间出现堆为空,说明因数数量没有k个,返回-1;反之,最后弹出的一个因数就是题解
3.解题代码
Python代码
import heapq
class Solution:
def kthFactor(self, n: int, k: int) -> int:
# 第一步,遍历,获取所有的因数并压入heap堆中
heap=[]
for i in range(1,int(n**0.5)+1):
if n%i==0:
heapq.heappush(heap,i)
if i!=n//i:
heapq.heappush(heap,n//i)
# print(heap)
# 第二步,遍历k次,从小到大从heap堆中弹出因数。如果中间出现堆为空,说明因数数量没有k个,返回-1;反之,最后弹出的一个因数就是题解
res=0
for i in range(k):
if len(heap)==0:
return -1
else:
res=heapq.heappop(heap)
return res
C++代码
class Solution {
public:
int kthFactor(int n, int k) {
priority_queue<int> pq;
for(int i=1;i<int(sqrt(n))+1;++i){
if(n%i==0){
pq.push(-i);
if(i!=n/i){
pq.push(-n/i);
}
}
}
int res=0;
for(int j=0;j<k;++j){
if(pq.size()==0){
return -1;
}else{
res=-pq.top();
pq.pop();
}
}
return res;
}
};