题目
有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。注意,不是必须有这些素因子,而是必须不包含其他的素因子。例如,前几个数按顺序应该是 1,3,5,7,9,15,21。
示例 1:
输入: k = 5
输出: 9
解题
方法一:优先队列 哈希表
思路
本题与 【优先队列, 动态规划, 多路归并】丑数 II 几乎相同。
方法一思路见:【优先队列, 动态规划, 多路归并】丑数 II - 方法一:小根堆(优先队列) 哈希表
代码
利用哈希表去重
class Solution {
static final int[] FACTORS = {3, 5, 7};
public int getKthMagicNumber(int k) {
Queue<Long> minHeap = new PriorityQueue<>();
Set<Long> seen = new HashSet<>();
minHeap.offer(1L);
seen.add(1L);
long num = -1;
while (k-- > 0) {
num = minHeap.poll();
for (int factor : FACTORS) {
long newNum = num * factor;
if (!seen.contains(newNum)) {
minHeap.offer(newNum);
seen.add(newNum);
}
}
}
return (int) num;
}
}
不使用哈希表去重
class Solution {
const int FACTORS[3] = {3, 5, 7};
public:
int getKthMagicNumber(int k) {
priority_queue<long long, vector<long long>, greater<long long>> min_heap;
long long num = -1, prev = -1;
min_heap.push(1L);
while (k--) {
num = min_heap.top();
min_heap.pop();
if (num == prev) {
++k;
continue;
}
for (const long long& factor : FACTORS) {
min_heap.push(num * factor);
}
prev = num;
}
return num;
}
};
方法二:动态规划 / 多路归并
思路
本题与 【优先队列, 动态规划, 多路归并】丑数 II 几乎相同。
方法二思路见:【优先队列, 动态规划, 多路归并】丑数 II - 方法二:动态规划 / 多路归并
代码
class Solution {
public int getKthMagicNumber(int k) {
long[] dp = new long[k];
dp[0] = 1;
for (int p3 = 0, p5 = 0, p7 = 0, i = 1; i < k; ++i) {
long n3 = dp[p3] * 3, n5 = dp[p5] * 5, n7 = dp[p7] * 7;
long min = Math.min(n3, Math.min(n5, n7));
dp[i] = min;
if (min == n3) ++p3;
if (min == n5) ++p5;
if (min == n7) ++p7;
}
return (int) dp[k - 1];
}
}
class Solution {
public:
int getKthMagicNumber(int k) {
long long dp[k];
dp[0] = 1;
for (int p3 = 0, p5 = 0, p7 = 0, i = 1; i < k; ++i) {
long long n3 = dp[p3] * 3, n5 = dp[p5] * 5, n7 = dp[p7] * 7;
long long mn = min(n3, min(n5, n7));
dp[i] = mn;
if (mn == n3) ++p3;
if (mn == n5) ++p5;
if (mn == n7) ++p7;
}
return dp[k - 1];
}
};
评论区