求表达式的第K个最小数（2 ^ x）*（3 ^ y）*（5 ^ z）
在表达中
2 x * 3 y * 5 z
x ， y和z可以取非负整数值（> = 0）。
因此该函数将生成一系列数字1,2,3,4,5,6,8,9,10,12,15,16....
- 我有一个powershell解决方案。
- 我基本上会以1开始循环，在每次迭代中，我会发现当前的数字因子是仅来自2,3或5的集合。
我想要的是一个优雅的算法。
这是一个面试问题。
这可以使用优先级队列来解决，您可以在其中存储按键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三胞胎为止。 删除的最后一个是你的答案。
实际上，这成为这种有向无环图的有序遍历。 （此处显示的前三个级别，实际图形当然是无限的）。
该页面列出了多种编程语言的解决方案。 像往常一样，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.Ordered有一个现成的函数，这是一个比我的merge更好的选择（它也有更好的名称）。
import Data.List.Ordered (union) hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming
我能想到的最简单的解决方案：
int[] factors = {2, 3, 5}; int[] elements = new int[k]; elements[0] = 1; int[] nextIndex = new int[factors.length]; int[] nextFrom = new int[factors.length]; for (int j = 0; j < factors.length; j++) { nextFrom[j] = factors[j]; } for (int i = 1; i < k; i++) { int nextNumber = Integer.MAX_VALUE; for (int j = 0; j < factors.length; j++) { if (nextFrom[j] < nextNumber) { nextNumber = nextFrom[j]; } } elements[i] = nextNumber; for (int j = 0; j < factors.length; j++) { if (nextFrom[j] == nextNumber) { nextIndex[j]++; nextFrom[j] = elements[nextIndex[j]] * factors[j]; } } } System.out.println(Arrays.toString(elements));
这在O（k）空间和时间中以升序生成该集合的前k元素。
请注意，有必要从提供它的所有 j中使用nextNumber以消除重复（毕竟2 * 3 = 3 * 2）。
编辑：该算法使用与nm发布的haskell相同的方法
这可能比您对算法的了解更多，包括您的思考方式，解决问题以及在团队中工作。
在开始之前，对问题进行适当的规范非常重要。 如上所述，一些未知因素包括：
- K有限制吗？
- 你想要一个已知的算法还是ad-hoc暴力好吗？
- 内存使用量与计算时间？ （也许一个或其他事项）
- 它有多快计算与我需要多长时间来开发它？
- 应该缓存结果吗？
向面试官询问部分或全部这些问题可能至少与能够回答所提问题一样重要。 当然，你可以用这种方式把自己画成一个角落，这甚至可以成为测试的一部分….
由于问题可以转换为找到Kth的最小数量
f(x,y,z) = x log(2) + y log(3) + z log(5),
该算法可能如下
- 以f（x，y，z）= f（0,0,0）开头
-
给定当前最小数f（i，j，k）= v，你必须找到（x，y，z）使得f（x，y，z）最接近v和> v。
log(2)我们可以说
0<=i-2<=x<=i+2, 0<=j-1<=y<=j+1 & 0<=k-1<=z<=k+1 such that f(x,y,z) > v
因此，这是为了在每个步骤中找到最少45个值，我会说它是O（K）算法。 当然，可以通过施加更多条件来减少数字45，例如（x，y，z）！=（i，j，k）。
这些是汉明数字 ，我在SRFI-41中用它作为例子。 这是我在那里使用的代码：
(define hamming (stream-cons 1 (stream-unique = (stream-merge < (stream-map (lsec * 2) hamming) (stream-map (lsec * 3) hamming) (stream-map (lsec * 5) hamming)))))
这种问题有一个非常优雅的解决方案。 算法和编码很简单。 时间复杂度为O（n）
我在某个地方看到了类似的问题。 问题是以升序生成2 ^ x.3 ^ yforms的数字。
所以这里。
int kthsmallest(int k){ int two = 0, three = 0, five = 0; int A[k]; A[0] = 1; for (int i=1; i
该算法基本上是 - 为x ， y ， z保留三个指针。 在代码中，我使用了两个 ， 三个和五个 。 在每次迭代中，检查哪一个较小（ 2 ^ x ， 3 ^ y或5 ^ z ）。 将该数字放在第i个索引中并增加x或y或z的相应值。 如果有多个min值，则递增两个指针。
下面是一个基于java的解决方案，用于查找第k个最小数，其中因子仅为2,3和5.这里2 * 3 * 5被认为是最小因子。
import java.util.Comparator; import java.util.PriorityQueue; public class KthSmallestFactor { public static void main(String[] args){ for(int i=1;i<=10;i++){ System.out.println(kthSmallest(i)); } } private static int kthSmallest(int k){ PriorityQueue p = new PriorityQueue (10, new Comparator () { public int compare(Triplet t1, Triplet t2) { int score1 = (int) (Math.pow(2, t1.a) * Math.pow(3, t1.b) * Math.pow(5, t1.c)) ; int score2 = (int) (Math.pow(2, t2.a) * Math.pow(3, t2.b) * Math.pow(5, t2.c)); return score1 -score2; } }); p.add(new Triplet(1, 1, 1)); int count =1; while(count
从x = y = z = 0开始; 在每次迭代中计算三个n：
nx = 2^(x+1)*3^y*5^z ny = 2^x*3^(y+1)*5^z nz = 2^x*3^y*5^(z+1)
找到三者中最少的n：
n = min(nx, ny, nz).
增加x，y或z：
If n == nx -> x = x + 1 If n == ny -> y = y + 1 If n == nz -> z = z + 1
在第K次迭代后停止并返回n。