java - Encuentra el Kth menos número para expresión(2 ^ x)*(3 ^ y)*(5 ^ z)
algorithm hamming-numbers (9)
En la expresion
2 x * 3 y * 5 z
Las x , y y z pueden tomar valores enteros no negativos (> = 0).
Entonces la función generaría una serie de números 1,2,3,4,5,6,8,9,10,12,15,16....
- Tengo una solución de fuerza bruta.
- Básicamente, repetiría en un bucle que comienza con 1 y en cada iteración encontraría si los factores numéricos actuales son solo del conjunto de 2,3 o 5.
Lo que me gustaría tener es un algoritmo elegante.
Esta es una pregunta de entrevista.
A continuación se muestra una solución basada en Java que funciona para encontrar el número más pequeño kth que tiene factores como solo 2,3 y 5. Aquí 2 * 3 * 5 se considera como el factor más pequeño.
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;
}
}
Comience con x = y = z = 0; En cada iteración calcula tres 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)
Encuentra la menor n entre las tres:
n = min(nx, ny, nz).
Aumente x, y, o z:
If n == nx -> x = x + 1
If n == ny -> y = y + 1
If n == nz -> z = z + 1
Deténgase después de la iteración K-th y regrese n.
Dado que el problema se puede convertir para encontrar K, el menor número de
f(x,y,z) = x log(2) + y log(3) + z log(5),
el algoritmo podría estar siguiendo
- comienza con f (x, y, z) = f (0,0,0)
dado el número mínimo actual f (i, j, k) = v, debe encontrar (x, y, z) de modo que f (x, y, z) sea el más cercano a v y> v. Desde
log(2)<log(3)<2log(2)<log(5)Podemos decir
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
Entonces, ya que esto es para encontrar el mínimo de 45 valores en cada paso y diría que es un algoritmo O (K). Por supuesto, el número 45 se puede reducir imponiendo más condiciones como (x, y, z)! = (I, j, k).
Esto podría estar probando más que su conocimiento de los algoritmos, para incluir cómo piensa, resuelve problemas y trabaja en equipo.
Es importante tener una especificación decente del problema antes de comenzar. Algunas de las incógnitas, como se describe, incluyen:
- ¿hay límites en K?
- ¿Desea un algoritmo conocido o está bien la fuerza bruta ad-hoc?
- uso de memoria vs tiempo de cálculo? (tal vez uno u otro asunto)
- ¿Qué tan rápido tiene que calcular vs cuánto tiempo tengo para desarrollarlo?
- ¿Deben los resultados ser cacheados?
Preguntarle al entrevistador sobre algunas o todas estas preguntas puede ser al menos tan importante como ser capaz de responder a la pregunta formulada. Por supuesto, puedes pintarte en un rincón de esta manera, que incluso puede ser parte de la prueba ...
Esto se puede resolver utilizando una cola de prioridad, donde almacena los tríos (x, y, z) ordenados por la clave 2 x 3 y 5 z .
Comience con solo el triplete (0, 0, 0) en la cola.
Elimine el triplete (x, y, z) con la clave más pequeña de la cola.
Inserte los tres tripletes (x + 1, y, z) , (x, y + 1, z) y (x, y, z + 1) en la cola. Asegúrate de no insertar nada que ya estuviera allí.
Repita desde el paso 2 hasta que haya quitado k tríos. El último eliminado es tu respuesta.
En efecto, esto se convierte en un recorrido ordenado de este gráfico acíclico dirigido. (Los primeros tres niveles que se muestran aquí, el gráfico real es por supuesto infinito).
Estos son los números de Hamming , que utilicé como ejemplo en SRFI-41 . Este fue el código que usé allí:
(define hamming
(stream-cons 1
(stream-unique =
(stream-merge <
(stream-map (lsec * 2) hamming)
(stream-map (lsec * 3) hamming)
(stream-map (lsec * 5) hamming)))))
Hay una solución muy elegante para este tipo de problema. El algoritmo y la codificación es simple. La complejidad del tiempo es O (n)
Vi un problema similar en alguna parte. El problema fue generar los números de la forma 2 ^ x.3 ^ y y en orden ascendente.
Así que aquí va.
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];
}
El algoritmo es básicamente: mantener tres punteros para x , y , z . En el código, utilicé dos , tres y cinco . En cada iteración, verifique cuál es más pequeña ( 2 ^ x , 3 ^ yo 5 ^ z ). Ponga ese número en el índice i e incremente el valor correspondiente de x o y o z . Si hay más de un valor mínimo, entonces incremente ambos punteros.
La solución más sencilla que se me ocurre:
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));
Esto genera los primeros k elementos de ese conjunto en orden ascendente en O (k) espacio y tiempo.
Tenga en cuenta que es necesario consumir el siguiente nextNumber de todos los j que lo proporcionan para eliminar los duplicados (2 * 3 = 3 * 2 después de todo).
Edición: el algoritmo usa el mismo enfoque que haskell publicado por nm
Esta página enumera soluciones en bazillion lenguajes de programación. Como de costumbre, la versión de Haskell es particularmente compacta y directa:
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
Actualizar Como Will Ness ha notado, hay una función lista en Data.List.Ordered que es una mejor opción que mi merge (y también tiene un nombre mejor).
import Data.List.Ordered (union)
hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming