题目链接:https://leetcode.cn/problems/get-kth-magic-number-lcci/
题目描述:
有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。
示例 1:
输入: k = 5
输出: 9
解法:小根堆
根据题目描述,满足条件的数,除了1,其他的都是3、5、7的倍数,我们可以将满足条件的数,进行排序,然后找到第K个数。我们可以使用一个小根堆来存储,小根堆自带的排序效果,可以快速的找到第K个数。
代码:
class Solution {
public int getKthMagicNumber(int k) {
int[] temp = {3,5,7};
Set<Long> set = new HashSet<>();
set.add(1L);
PriorityQueue<Long> queue = new PriorityQueue<>();
queue.offer(1L);
int result = 0;
for(int i = 0;i<k;i++) {
long poll = queue.poll();
result = (int) poll;
for(int t : temp) {
long l = poll * t;
if(set.add(l)) {
queue.offer(l);
}
}
}
return result;
}
}