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

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

这可以使用优先级队列来解决,您可以在其中存储按键2 ^x 3 ^y 5 ^z排序的三元组(x,y,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三胞胎.删除的最后一个是你的答案.

实际上,这成为这种有向无环图的排序遍历.(此处显示的前三个级别,实际图形当然是无限的).

Answer 2

此页面列出了bazillion编程语言的解决方案.像往常一样,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

更新如同Ness已经注意到,有一个现成的功能,Data.List.Ordered其中一个比我更好的选择merge(它也有一个更好的名称).

import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming

Answer 3

我能想到的最简单的解决方案:

    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));

这将k在O(k)空间和时间中按升序生成该集合的第一个元素.

请注意,必须nextNumber从提供它的所有内容 j中消耗,以消除重复(毕竟2*3 = 3*2).

编辑:该算法使用与nm发布的haskell相同的方法

Answer 4

这可能比您对算法的了解更多,包括您的思考方式,解决问题以及在团队中工作.

在开始之前,对问题进行适当的规范非常重要.如上所述,一些未知因素包括:

• K有界限吗？
• 你想要一个已知的算法还是ad-hoc暴力好吗？
• 内存使用量与计算时间？(也许一个或其他事项)
• 它有多快计算与我需要多长时间来开发它？
• 应该缓存结果吗？

向面试官询问部分或全部这些问题可能至少与能够回答所提问题一样重要.当然,你可以用这种方式把自己画成一个角落,这甚至可以成为测试的一部分....