java - 找到表达式 (2^x)*(3^y)*(5^z) 的第 K 个最小数

Question

在表达式中

2^x * 3^y * 5^z

x、y 和z 可以取非负整数值(>=0)。

所以函数会生成一系列数字1,2,3,4,5,6,8,9,10,12,15,16....

• 我有一个蛮力解决方案。
• 我基本上会在从 1​​ 开始的循环中进行迭代，并且在每次迭代中，我会发现当前的数字因子是否仅来自 2,3 或 5 的集合。

我想要的是一个优雅的算法。

这是一道面试题。

Answer 1

这可以使用优先级队列来解决，其中存储三元组 (x, y, z) 按键 2^x3 ^排序y5^z.

1. 仅从队列中的三元组 (0, 0, 0) 开始。

2. 从队列中移除键最小的三元组(x, y, z)。

3. 插入三个三元组(x+1, y, z), (x, y+1, z) 和 (x, y, z+1) 在队列中。确保您没有插入任何已经存在的内容。

4. 从第 2 步开始重复，直到删除 k 个三元组。删除的最后一个是您的答案。

实际上，这变成了这个有向无环图的排序遍历。 (这里显示的前三个级别，实际的图形当然是无限的)。