Найдите K-е наименьшее число для выражения ( 2 ^ x) * (3 ^ y) * (5 ^ z)

Question

Найдите 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 ....

У меня есть грубая сила решение.
Я бы в основном выполнял итерацию в цикле, начиная с 1, и на каждой итерации я бы обнаружил, являются ли текущие числовые коэффициенты только из набора 2,3 или 5.

Я бы хотел иметь элегантный алгоритм .

Это вопрос из интервью.

23

java algorithm hamming-numbers

задан Will Ness 5 May 2012 в 01:16

3 ответа

Другие вопросы по тегам:

java algorithm hamming-numbers

Похожие вопросы:

score 11 · Answer 1

Самое простое решение, которое я могу придумать:

    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 в конце концов).

Редактировать: алгоритм использует тот же подход, что и в haskell, опубликованном n.m.

score 2 · Answer 2

Поскольку задачу можно преобразовать в нахождение K-го наименьшего числа из

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

score 1 · Answer 3

Существует очень элегантное решение этой проблемы. Алгоритм и кодирование просты. Сложность по времени составляет 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 ). Поместите это число в индекс ith и увеличьте соответствующее значение x или y или z . Если существует более одного минимального значения, то увеличивайте оба указателя.