Recientemente vi este código Javascript en StackOverflow para fusionar dos matrices y eliminar duplicados:
Array.prototype.unique = function() {
var a = this.concat();
for(var i=0; i<a.length; ++i) {
for(var j=i+1; j<a.length; ++j) {
if(a[i] === a[j])
a.splice(j--, 1);
}
}
return a;
};
var array1 = ["Vijendra","Singh"];
var array2 = ["Singh", "Shakya"];
var array3 = array1.concat(array2).unique();
Si bien este código funciona, es terriblemente ineficiente ( O(n^2)
). Su desafío es hacer un algoritmo con menos complejidad.
El criterio ganador es la solución con la menor complejidad , pero los lazos se romperán por la longitud más corta en caracteres.
Requisitos :
Empaquete todo su código en una función que cumpla con los siguientes requisitos de "corrección":
- Entrada: dos matrices
- Salida: una matriz
- Fusiona elementos de ambas matrices juntas: cualquier elemento en cualquier matriz de entrada debe estar en la matriz de salida.
- La matriz de salida no debe tener duplicados.
- El orden no importa (a diferencia del original)
- Cualquier idioma cuenta
- No utilice las funciones de matriz de la biblioteca estándar para detectar unicidad o fusionar conjuntos / matrices (aunque otras cosas de la biblioteca estándar están bien). Permítanme hacer la distinción de que la concatenación de matriz está bien, pero las funciones que ya hacen todo lo anterior no lo están.
[1, 2, 2, 3]
y[2, 3, 4]
volver[1, 2, 2, 3, 4]
o[1, 2, 3, 4]
?Respuestas:
Perl
27 caracteres
Hack Perl simple
Estoy seguro de que alguien podría decir esto ... y así (Gracias Dom Hastings)
fuente
sub x{$_{$_}++for@_;keys%_}
(en caso de que se reduzca a un empate) y usar como:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Versión de golf:
Versión de golf legible para humanos:
Podría usar
concat
así y hacerlo en 86 caracteres:Pero no estoy seguro de si todavía es O (N) basado en este JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping ya que la versión concat es marginalmente más rápida con matrices más pequeñas pero más lenta con matrices más grandes (Chrome 31 OSX).
En la práctica, haga esto (el golf está lleno de malas prácticas):
No soy bueno en la complejidad informática, pero creo que esto es así
O(N)
. Me encantaría si alguien pudiera aclarar.Editar: Aquí hay una versión que toma cualquier número de matrices y las combina.
fuente
O(N)
.O(A*B)
(no se usaN
porque es confuso). Sería que si cada matriz de entrada (cadaA
) tuviera la misma cantidad de elementos (B
) que en realidadO(SUM(B) FOR ALL A)
, se puede reescribir comoO(N)
cuando se defineN
como el recuento de elementos de todas las entradas de la matriz.Python 2.7, 38 caracteres
Debe ser O (N) asumiendo una buena función hash.
La
set
implementación de 8 caracteres de Wasi es mejor, si no crees que viola las reglas.fuente
PHP,
69/4268/41 caracteresLa inclusión de la declaración de función es de 68 caracteres:
Sin incluir la declaración de función es de 41 caracteres:
fuente
Una forma en Ruby
Para mantenerme dentro de las reglas descritas anteriormente, usaría una estrategia similar a la solución de JavaScript y usaría un hash como intermediario.
Esencialmente, estos son los pasos que estoy siguiendo en la línea de arriba.
merged_arr
que contendrá el resultado.Object#tap
para llenar el hash (referenciado comohash
en eltap
bloque) y devolverlo para el encadenamiento del método posteriorarr1
yarr2
formar una única matriz sin procesarel
de la matriz concatenada, poner el valorel
enhash[el]
si no hay valor dehash[el]
existe actualmente. La memoria aquí (hash[el] ||= el
) es lo que garantiza la unicidad de los elementos.Esto debería correr a
O(n)
tiempo. Avíseme si he hecho declaraciones inexactas o si puedo mejorar la respuesta anterior, ya sea por eficiencia o legibilidad.Posibles mejoras.
El uso de la memorización es probablemente innecesario dado que las claves del hash serán únicas y los valores son irrelevantes, por lo que esto es suficiente:
Realmente me encanta
Object#tap
, pero podemos lograr el mismo resultado usandoEnumerable#reduce
:Incluso podrías usar
Enumberable#map
:Cómo lo haría en la práctica
Habiendo dicho todo eso, si me pidieran fusionar dos matrices
arr1
yarr2
que el resultadomerged_arr
tuviera elementos únicos y pudiera usar cualquier método de Ruby a mi disposición, simplemente usaría el operador de unión de conjunto que está destinado a resolver este problema exacto:Sin
Array#|
embargo, un vistazo rápido a la fuente parece confirmar que el uso de un hash como intermediario parece ser la solución aceptable para realizar una fusión única entre 2 matrices.fuente
Una función que tomaría n matrices podría ser la siguiente:
Golfizado, creo que esto debería funcionar (117 caracteres)
Actualización Si desea conservar el tipo original, puede
o golf 149:
Esto todavía puede arrojar algunas dudas, si quieres distinguir
123
y'123'
, entonces, esto no funcionaría ...fuente
O(N)
)?m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])
se convierte en["1", "2", "3", "4", "5", "6", "7"]
pitón, 46
O, usando la operación de configuración simplemente
pitón, 8
fuente
Perl
23 bytes, si solo contamos el bloque de código dentro de la subrutina. Podría ser 21, si se permite sobrescribir valores globales (se eliminaría
my
del código). Devuelve elementos en orden aleatorio, porque el orden no importa. En cuanto a la complejidad, en promedio es O (N) (depende del número de colisiones de hash, pero son bastante raras; en el peor de los casos, puede ser O (N 2 ) (pero esto no debería suceder, porque Perl puede detectar hashes patológicos , y cambia la semilla de la función hash cuando detecta dicho comportamiento)).Salida (que también muestra aleatoriedad):
fuente
Fortran:
282252233213Versión de golf:
Que no solo se ve infinitamente mejor, sino que realmente se compilará (una línea demasiado larga en su forma de golf) con la forma legible por humanos:
Esto debería ser
O(n)
tan copioa
enc
y después comprobar cada unob
contra todosc
. El último paso es eliminar la basura quec
contendrá ya que no está inicializada.fuente
Mathematica 10 Chars
Ejemplo:
Mathematica2 43 caracteres
fuente
Tally[Join[a, b]][[;; , 1]]
que también sería trampa ;-) Por cierto, podría guardar caracteres mediante el uso de variables de una sola letra.Javascript 86
Versión de golf:
Versión legible:
fuente
m([1,0,0,0,0],[0,1,0])
regresa[1]
.h[v]=v
ah[v]=1
.JavaScript 60
Estoy usando el generador ES6.
Lo siguiente es comprobable usando Traceur REPL de Google .
fuente
Si está buscando una implementación basada en JavaScript que se base en los Objetos subyacentes detrás del marco para ser eficiente, simplemente hubiera usado Set. Generalmente en una implementación, el objeto Set maneja inherentemente objetos únicos durante la inserción con algún tipo de indexación de búsqueda binaria. Sé que en Java es una
log(n)
búsqueda, usando búsqueda binaria basada en el hecho de que ningún conjunto puede contener un solo objeto más de una vez.Si bien no tengo idea si esto también es cierto para Javascript, algo tan simple como el siguiente fragmento puede ser suficiente para una
n*log(n)
implementación:JavaScript , 61 bytes
Pruébalo en línea!
Si el fragmento anterior usa
a = [1,2,3]
yb = [1,2,3,4,5,6]
luegos=[1,2,3,4,5,6]
.Si conoce la complejidad de la
Set.add(Object)
función en JavaScript, hágamelo saber, la complejidad de esto esn + n * f(O)
dóndef(O)
está la complejidad des.add(O)
.fuente
APL (Dyalog Unicode) , O (N), 28 bytes
Función de infijo tácito anónimo.
Pruébalo en línea!
,
concatenar los argumentos; EN)(
...)
aplique la siguiente función tácita anónima en eso; O (1)⍳⍨
índices selfie (índices de la primera aparición de cada elemento en toda la matriz); EN)=
compare elemento por elemento con; EN):⍳∘≢
índices de la longitud de la matriz; EN)(/⍨)
usar eso para filtrar; EN):⊢
el argumento no modificado; O (1)O (N + 1 + N + N + N + N + 1) = O (N)
fuente
JavaScript, 131 caracteres
fuente
PHP alrededor de 28 caracteres [omitiendo las variables de matriz de ejemplo y la variable de resultado].
$ array1 = array (1, 2, 3); $ array2 = array (3, 4, 5);
$ resultado = array_merge ($ array1, $ array2);
fuente