Combinación de matrices sin duplicados

15

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.
hkk
fuente
¿Cómo se supone que debemos crear o agregar a una matriz sin usar las funciones de la matriz?
Emil Vikström
@ EmilVikström Ver mi edición. Quise decir que no puedes usar funciones de unicidad de matriz. Perdón por no estar claro.
HK
Si uno de los arreglos tiene duplicados, ¿los eliminamos también? Por ejemplo, ¿debería fusionarse [1, 2, 2, 3]y [2, 3, 4]volver [1, 2, 2, 3, 4]o [1, 2, 3, 4]?
OI
1
@OI Sí, eso lo haría demasiado fácil.
HK
1
¿Puedo preguntar: matrices de qué ? ¿Podemos suponer simplemente números enteros o cadenas, o también tenemos que permitir cosas más complejas como objetos multinivel?
jawns317

Respuestas:

8

Perl

27 caracteres

Hack Perl simple

my @vals = ();
push @vals, @arr1, @arr2;
my %out;
map { $out{$_}++ } @vals;
my @unique = keys %out;

Estoy seguro de que alguien podría decir esto ... y así (Gracias Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Zach Leighton
fuente
1
"No utilice las funciones de matriz de la biblioteca estándar para detectar la unicidad (aunque otras cosas forman la biblioteca estándar está bien)"
John Dvorak
1
¿Cómo estoy violando esa regla? No estoy usando funciones únicas?
Zach Leighton el
¿Cómo funciona entonces? Lo siento, no puedo leer Perl. Si lee las claves de un mapa hash, ¿eso cuenta como correcto con esa regla? No votaré hasta estar convencido de que lo es.
John Dvorak
1
Combina las matrices, realiza un bucle sobre ambas y agrega a un hash que incrementa el valor cuya clave es el valor actual en el bucle de la matriz. Luego toma las claves de ese hash, lo he usado en algunos de mis trabajos ... Entonces [1,1,2,3,4,4] se convierte en {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Zach Leighton
@ZachLeighton puede acortar el código a 27 caracteres con 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))
Dom Hastings
10

JavaScript O (N) 131 124 116 92 (86?)

Versión de golf:

function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}

Versión de golf legible para humanos:

function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}

Podría usar concatasí y hacerlo en 86 caracteres:

function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}

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

function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i < a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i < a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));

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.

function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i < args.length; i++) {
      for (var j = 0; j < args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));
George Reith
fuente
Esto es casi exactamente lo que iba a publicar en un par de segundos :-( Sí, se amortiza el tiempo lineal si se implementan tablas hash con tiempo constante amortizado para la inserción y la búsqueda (que es común en muchos idiomas, no lo sé específicamente sobre JS).
Emil Vikström
@ EmilVikström Gracias por eso, creo que JavaScript sí, pero no tengo pruebas al respecto. Disculpas por tener dedos rápidos, disminuyó la velocidad con comentarios: P
George Reith
Este es un gran enfoque. Sin embargo, ¿podría proporcionar una solución de estilo de "código de golf" además de su versión bien formateada? Al ver que varias personas han pensado en esto como el enfoque correcto, probablemente habrá un empate O(N).
HK
@ cloudcoder2000 Ok, quería imprimir una versión completa ya que es probable que la versión de código de golf sea menos eficiente en la práctica.
George Reith
1
@ cloudcoder2000 No son completamente independientes, por lo que el peor de los casos no lo es O(A*B)(no se usa Nporque es confuso). Sería que si cada matriz de entrada (cada A) tuviera la misma cantidad de elementos ( B) que en realidad O(SUM(B) FOR ALL A), se puede reescribir como O(N)cuando se define Ncomo el recuento de elementos de todas las entradas de la matriz.
meiamsome
4

Python 2.7, 38 caracteres

F=lambda x,y:{c:1 for c in x+y}.keys()

Debe ser O (N) asumiendo una buena función hash.

La setimplementación de 8 caracteres de Wasi es mejor, si no crees que viola las reglas.

Keith Randall
fuente
¡Agradable! Las comprensiones en Python pueden ser tan elegantes y poderosas.
OI
3

PHP, 69/42 68/41 caracteres

La inclusión de la declaración de función es de 68 caracteres:

function m($a,$b){return array_keys(array_flip($a)+array_flip($b));}

Sin incluir la declaración de función es de 41 caracteres:

array_keys(array_flip($a)+array_flip($b))
zamnuts
fuente
3

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.

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] ||= el } }.keys

Esencialmente, estos son los pasos que estoy siguiendo en la línea de arriba.

  1. Definir una variable merged_arrque contendrá el resultado.
  2. Inicialice un hash vacío y sin nombre como intermediario para poner elementos únicos en
  3. Use Object#tappara llenar el hash (referenciado como hashen el tapbloque) y devolverlo para el encadenamiento del método posterior
  4. Concatenar arr1y arr2formar una única matriz sin procesar
  5. Para cada elemento elde la matriz concatenada, poner el valor elen hash[el]si no hay valor de hash[el]existe actualmente. La memoria aquí ( hash[el] ||= el) es lo que garantiza la unicidad de los elementos.
  6. Obtenga las claves (o los valores, ya que son los mismos) para el hash ahora poblado

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:

merged_arr = {}.tap { |hash| (arr1 + arr2).each { |el| hash[el] = 1 } }.keys

Realmente me encanta Object#tap, pero podemos lograr el mismo resultado usando Enumerable#reduce:

merged_arr = (arr1 + arr2).reduce({}) { |arr, val| arr[val] = 1; arr }.keys

Incluso podrías usar Enumberable#map:

merged_arr = Hash[(arr1 + arr2).map { |val| [val, 1] }].keys

Cómo lo haría en la práctica

Habiendo dicho todo eso, si me pidieran fusionar dos matrices arr1y arr2que el resultado merged_arrtuviera 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:

merged_arr = arr1 | arr2

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.

OI
fuente
"No utilice las funciones de matriz de la biblioteca estándar para detectar la unicidad (aunque otras cosas forman la biblioteca estándar está bien)"
John Dvorak
¿Cómo estoy violando esa regla en el segundo ejemplo? La memorización se realiza en un hash. ¿Eso tampoco está permitido?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Una función que tomaría n matrices podría ser la siguiente:

function m()
{
  var o={},a=arguments,c=a.length,i;
  while(c--){i=a[c].length;while(i--)o[a[c][i]] = true} 
  return Object.keys(o);
}

Golfizado, creo que esto debería funcionar (117 caracteres)

function m(){var o={},a=arguments,c=a.length,i;while(c--){i=a[c].length;while(i--)o[a[c][i]]=1}return Object.keys(o)}

Actualización Si desea conservar el tipo original, puede

function m()
{
  var o={},a=arguments,c=a.length,f=[],g=[];
  while(c--)g.concat(a[c])
  c = g.length      
  while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}
  return f
}

o golf 149:

function m(){var o={},a=arguments,c=a.length,f=[],g=[];while(c--)g.concat(a[c]);c= g.length;while(c--){if(!o[g[c]]){o[g[c]]=1;f.push(g[c])}}return f}

Esto todavía puede arrojar algunas dudas, si quieres distinguir 123y '123', entonces, esto no funcionaría ...

Konijn
fuente
Gracias por la respuesta. Es impresionantemente corto, sin embargo, esto solo soluciona la mitad del problema. También debe incluir en la solución la parte de fusión real (incluso si es la misma que en el ejemplo original) y poner todo junto en una función. Además, ¿podría proporcionar una versión "golfizada" además de esto (como está O(N))?
HK
Esto convierte a todos los miembros en cadenas. por ejemplo, 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"]
George Reith
2

pitón, 46

def A(a,b):print[i for i in b if i not in a]+a

O, usando la operación de configuración simplemente

pitón, 8

set(a+b)
Wasi
fuente
1
Lo sentimos, no estaba claro, el uso de operaciones de configuración también es trampa.
HK
Su primer código tendrá duplicados si hay duplicados en a o si hay duplicados en by ese elemento no está en a.
Vedant Kandoi
2

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

use 5.010;
sub unique{
    my%a=map{$_,1}@_;keys%a
}
my @a1 = (1, 2, 3, 4);
my @a2 = (3, 4, 5, 6);
say join " ", unique @a1, @a2;

Salida (que también muestra aleatoriedad):

/tmp $ perl unique.pl 
2 3 4 6 1 5
/tmp $ perl unique.pl 
5 4 6 2 1 3
Konrad Borowski
fuente
2

Fortran: 282 252 233 213

Versión de golf:

function f(a,b,m,n) result(d);integer::m,n,a(m),b(n),c(m+n);integer,allocatable::d(:);j=m+1;c(1:m)=a(1:m);do i=1,n;if(.not.any(b(i)==c(1:m)))then;c(j)=b(i);j=j+1;endif;enddo;allocate(d(j-1));d=c(1:j-1);endfunction

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:

function f(a,b,m,n) result(d)
  integer::m,n,a(m),b(n),c(m+n)
  integer,allocatable::d(:)
  j=m+1;c(1:m)=a(1:m)
  do i=1,n
     if(.not.any(b(i)==c(1:m)))then
        c(j)=b(i);j=j+1
     endif
  enddo
  allocate(d(j-1))
  d=c(1:j-1)
end function

Esto debería ser O(n)tan copio aen cy después comprobar cada uno bcontra todos c. El último paso es eliminar la basura que ccontendrá ya que no está inicializada.

Kyle Kanos
fuente
2

Mathematica 10 Chars

Union[a,b]

Ejemplo:

a={1,2,3,4,5};
b={1,2,3,4,5,6};
Union[a,b]

{1, 2, 3, 4, 5, 6}

Mathematica2 43 caracteres

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Murta
fuente
8
Creo que esto iría en la categoría de usar métodos de matriz de biblioteca estándar.
HK
Hola @ cloudcoder2000. No es necesario llamar a una biblioteca específica para usar Union en Mathematica.
Murta
55
En mi opinión, usar una función integrada para hacer exactamente lo que la pregunta está haciendo es hacer trampa.
Konrad Borowski
ok ok .. el segundo código no usa Union.
Murta
1
Supongo 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.
Yves Klett
1

Javascript 86

Versión de golf:

function m(a,b){var h={};return a.concat(b).filter(function(v){return h[v]?0:h[v]=1})}

Versión legible:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
fuente
1
Esto ignora los valores de falsey ... m([1,0,0,0,0],[0,1,0])regresa [1].
George Reith
1
Cambiar h[v]=va h[v]=1.
George Reith
Bien visto @GeorgeReith! Pasamos de 86 a 84 :)
Bertrand
Todavía es 86, creo que te confundiste porque eliminaste 2 caracteres de la versión legible, no la de golf.
George Reith
1

JavaScript 60

Estoy usando el generador ES6.
Lo siguiente es comprobable usando Traceur REPL de Google .

m=(i,j)=>{h={};return[for(x of i.concat(j))if(!h[x])h[x]=x]}
Florent
fuente
0

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

var s = new Set(a);      // Complexity O(a.length)
b.forEach(function(e) {  // Complexity O(b.length) * O(s.add())
  s.add(e);
}); 

Pruébalo en línea!


Si el fragmento anterior usa a = [1,2,3]y b = [1,2,3,4,5,6]luego s=[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 es n + n * f(O)dónde f(O)está la complejidad de s.add(O).

Urna de pulpo mágico
fuente
0

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)

Adán
fuente
-2

JavaScript, 131 caracteres

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
fuente
44
Bienvenido a PPCG! Díganos qué idioma es este y formateelo como código para una mejor lectura. (Esto funciona al sangrar las líneas de código con cuatro espacios). También se agradecería una explicación de su enfoque.
Laikoni
es solo un código javascript.
deepak_pal
@techdeepak Puede agregar esa información vital a su publicación, formatearla correctamente, agregar resaltado de sintaxis y escribir un poco más sobre la complejidad de su algoritmo, ya que este es el algoritmo más rápido . Tal como está, esta publicación es de bastante baja calidad.
Jonathan Frech
-2

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

Endri
fuente
De la pregunta: no use las funciones de matriz de la biblioteca estándar para detectar unicidad o fusionar conjuntos / matrices . Además, esto en realidad no elimina los duplicados de la matriz
Jo King,
Creo que ha pasado por alto esta importante línea de la pregunta: " No use las funciones de matriz de la biblioteca estándar para detectar unicidad o fusionar conjuntos / matrices "
Peter Taylor
Si. Eso es correcto. Gracias a todos por señalar eso. Críticas humildemente aceptadas.
Endri
@jo king. Tiene toda la razón sobre "No utilizar bibliotecas estándar ...". El resto está mal. Elimina los duplicados. php.net/manual/en/function.array-merge.php . Le recomiendo que lea completamente la documentación de PHP. Estoy 100% seguro de que hace el trabajo. Solo necesita tener cuidado con cuál de los arreglos considera duplicados. Salud.
Endri
1
Literalmente ejecuté el código en su envío sin cambios y la salida tiene duplicados. Parece que debería leer la documentación, es decir, si, sin embargo, las matrices contienen claves numéricas, el valor posterior no sobrescribirá el valor original, sino que se agregará
Jo King