查找表达式 （2^x）*（3^y）*（5^z） 的第 K 个最小数
2022-09-01 21:40:29
在表达式中
2x * 3y * 5z
和 可以采用非负整数值 （>=0）。xyz
因此，该函数将生成一系列数字1,2,3,4,5,6,8,9,10,12,15,16....
- 我有一个蛮力解决方案。
- 我基本上会在从1开始的循环中迭代，在每次迭代中，如果当前数字因子仅来自2，3或5的集合，我会发现。
我想要的是一个优雅的算法。
这是一个面试问题。
答案 1
这可以使用优先级队列来解决，您可以在其中存储按键2 x 3 y 5 z排序的三元组（x，y，z）。
仅从队列中的三元组 （0， 0， 0） 开始。
从队列中删除具有最小键的三元组 （x， y， z）。
在队列中插入三个三元组 （x+1， y， z）、 （x， y+1， z） 和 （x， y， z+1）。确保不要插入任何已经存在的内容。
从步骤 2 开始重复，直到删除了 k 个三元组。最后一个被删除的是你的答案。
实际上，这成为此有向无环图的排序遍历。（这里显示的前三个层次，实际的图形当然是无限的）。
答案 2
本页列出了大量编程语言的解决方案。像往常一样，Haskell版本特别紧凑和直接：
hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
where merge (x:xs) (y:ys)
| x < y = x : xs `merge` (y:ys)
| x > y = y : (x:xs) `merge` ys
| otherwise = x : xs `merge` ys
更新正如Will Ness所指出的，有一个现成的功能，它比我的更好选择（它也有一个更好的名字）。Data.List.Orderedmerge
import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming
推荐
