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

这可以使用优先级队列来解决，其中存储按键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

此页面列出了无数种编程语言的解决方案。像往常一样，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

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有界限吗？
• 你想要一个已知的算法还是临时蛮力可以？
• 内存使用与计算时间？（可能是其中之一）
• 计算速度有多快与开发它需要多少时间？
• 结果应该被缓存吗？

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

Answer 5

由于问题可以转化为找到第 K 个最少的

 f(x,y,z) = x log(2) + y log(3) + z log(5),

该算法可能会遵循

1. 以 f(x,y,z) = f(0,0,0) 开头

2. 给定当前最小数 f(i,j,k) = v，你必须找到 (x,y,z) 使得 f(x,y,z) 最接近 v 并且 > v。因为

   log(2)<log(3)<2log(2)<log(5)

   我们可以说

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

Answer 6

这些是汉明数，我在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)))))

Answer 7

这种问题有一个非常优雅的解决方案。算法和编码很简单。时间复杂度为 O(n)

我在某处看到了类似的问题。问题是按升序生成 2^x.3^y 形式的数字。

所以这里。

int kthsmallest(int k){

    int two = 0, three = 0, five = 0;
    int A[k];
    A[0] = 1;
    for (int i=1; i<k; i++){
        int min = (A[two] * 2 <= A[three] * 3)? A[two] * 2: A[three] * 3;
        min = (min <= A[five] * 5)? min: A[five] * 5;
        A[i] = min;
        if (min == A[two] * 2)
            two++;
        if (min == A[three] * 3)
            three++;
        if (min == A[five] * 5)
            five++;
    }
    return A[k-1];
}

该算法基本上是 - 为x、y、z保留三个指针。在代码中，我使用了二、三和五。在每次迭代中，检查哪个更小（2^x、3^y或5^z）。将该数字放在第i 个索引中，并增加x或y或z的相应值。如果有超过一个最小值，则增加两个指针。

Answer 8

下面是一个有效的基于 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<Triplet> p = new PriorityQueue<Triplet>(10, new Comparator<Triplet>() {
            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 <k){
            Triplet top = p.poll();
            count++;
            int a = top.a;
            int b = top.b;
            int c = top.c;
            Triplet t = new Triplet(a+1, b, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b+1, c);
            if(!p.contains(t)){
                p.add(t);
            }
            t = new Triplet(a, b, c+1);
            if(!p.contains(t)){
                p.add(t);
            }
        }
        Triplet kth = p.poll();
        System.out.println("a: "+kth.a+"b: "+kth.b+"c: "+kth.c);
        return (int) (Math.pow(2, kth.a) * Math.pow(3, kth.b) * Math.pow(5, kth.c));
    }
}
class Triplet{
    int a ;
    int b;
    int c;

    public Triplet(int a , int b, int c){
        this.a = a;
        this.b=b;
        this.c = c;
    }

    public boolean equals(Object other){
        Triplet t = (Triplet)other;
        return this.a== t.a && this.b==t.b && this.c == t.c; 
    }
}

Answer 9

从 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。