Mesclagem de matrizes sem duplicatas

15

Vi recentemente esse código Javascript no StackOverflow para mesclar duas matrizes e remover duplicatas:

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

Enquanto esse código funciona, é terrivelmente ineficiente ( O(n^2)). Seu desafio é criar um algoritmo com menos complexidade.

O critério vencedor é a solução com a menor complexidade , mas os vínculos serão quebrados pelo menor comprimento de caracteres.

Requisitos :

Empacote todo o seu código em uma função que atenda aos seguintes requisitos de "correção:"

  • Entrada: duas matrizes
  • Saída: Uma matriz
  • Mescla elementos de ambas as matrizes - Qualquer elemento em qualquer matriz de entrada deve estar na matriz de saída.
  • A matriz gerada não deve ter duplicatas.
  • O pedido não importa (diferente do original)
  • Qualquer idioma conta
  • Não use as funções de matriz da biblioteca padrão para detectar exclusividade ou mesclar conjuntos / matrizes (embora outras coisas da biblioteca padrão estejam corretas). Deixe-me fazer a distinção de que a concatenação de matriz é boa, mas as funções que já fazem todas as opções acima não são.
hkk
fonte
Como devemos criar ou anexar a uma matriz sem usar as funções da matriz?
Emil Vikström
@ EmilVikström Veja minha edição. Eu quis dizer que você não pode usar funções de exclusividade de matriz. Desculpe por não estar claro.
precisa saber é o seguinte
Se uma das matrizes tiver duplicatas, também as removeremos? Por exemplo, deve mesclar [1, 2, 2, 3]e [2, 3, 4]retornar [1, 2, 2, 3, 4]ou [1, 2, 3, 4]?
OI
1
@ Oi Sim, isso tornaria muito fácil.
Hck 02/01
1
Posso perguntar: matrizes de quê ? Podemos assumir simplesmente números inteiros ou seqüências de caracteres, ou também precisamos permitir coisas mais complexas, como objetos de vários níveis?
precisa saber é o seguinte

Respostas:

8

Perl

27 caracteres

Simple Perl Hack

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

Tenho certeza de que alguém poderia dizer isso de uma só vez ... e assim (Obrigado Dom Hastings)

sub x{$_{$_}++for@_;keys%_}
Zach Leighton
fonte
1
"Não use funções de matriz da biblioteca padrão para detectar singularidade (embora outras coisas formam a biblioteca padrão está bem)"
John Dvorak
1
Como estou violando essa regra? Eu não estou usando funções únicas?
Zach Leighton
Como funciona, então? Desculpe, não consigo ler perl. Se ele lê as chaves de um mapa de hash - isso conta como OK com essa regra? Não vou votar até convencido de que é.
John Dvorak
1
Ele combina as matrizes, faz um loop sobre as duas e adiciona a um hash incrementando o valor who's key é o valor atual no loop da matriz. Depois, pega as chaves desse hash, usei isso em alguns dos meus trabalhos. Então, [1,1,2,3,4,4] se torna {1 => 2, 2 => 1, 3 => 1 , 4 => 2}
Zach Leighton
@ZachLeighton você pode encurtar o código para 27 caracteres com sub x{$_{$_}++for@_;keys%_}(no caso de empate!) E usar como:z((1,2,3,4),(2,3,4,5,6))
Dom Hastings
10

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

Versão Golfed:

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}

Versão golfada legível humana:

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
}

eu poderia usar concat assim e fazê-lo em 86 caracteres:

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

Mas não tenho certeza se ainda é O (N) baseado neste JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping, pois a versão concat é marginalmente mais rápida com matrizes menores, mas mais lenta com matrizes maiores (Chrome 31 OSX).

Na prática, faça isso (o golfe é cheio de más práticas):

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

Não sou bom em complexidade de computação, mas acredito que sim O(N). Adoraria se alguém pudesse esclarecer.

Editar: Aqui está uma versão que pega qualquer número de matrizes e as mescla.

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
fonte
Isso é quase exatamente o que eu publicaria em alguns segundos :-( Sim, é tempo linear amortizado se tabelas de hash forem implementadas com tempo constante amortizado para inserção e pesquisa (que é comum em muitos idiomas, não sei especificamente sobre JS).
Emil Vikström
@ EmilVikström Obrigado por acreditar que o JavaScript possui, mas não tem provas. Desculpas por ter dedos rápidos, desacelerou-se para baixo com os comentários: P
George Reith
Essa é uma ótima abordagem. No entanto, você também poderia fornecer uma solução no estilo "código-golfe", além da sua versão bem formatada? Vendo que várias pessoas pensaram nisso como a abordagem correta, provavelmente haverá um empate O(N).
Hck 02/01
@ cloudcoder2000 Ok, eu queria imprimir uma versão completa, pois a versão code-golf provavelmente será menos eficiente na prática.
George Reith
1
@ cloudcoder2000 Eles não são totalmente independentes, então o pior caso não é O(A*B)( não está sendo usado Nporque é confuso). Seria que se toda matriz de entrada (toda A) tivesse a mesma quantidade de elementos ( B) que é atualmente O(SUM(B) FOR ALL A), que pode ser reescrita como O(N)na definição Nda contagem de elementos de todas as entradas da matriz.
meiamsome
4

Python 2.7, 38 caracteres

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

Deve ser O (N) assumindo uma boa função de hash.

A setimplementação de 8 caracteres de Wasi é melhor, se você não acha que isso viola as regras.

Keith Randall
fonte
Agradável! Compreensões no Python podem ser tão elegantes e poderosas.
OI
3

PHP, 69/42 68/41 caracteres

A declaração da função inclui 68 caracteres:

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

A não inclusão da declaração da função possui 41 caracteres:

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

Uma maneira em Ruby

Para manter as regras descritas acima, eu usaria uma estratégia semelhante à solução JavaScript e usaria um hash como intermediário.

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

Essencialmente, estas são as etapas que estou executando na linha acima.

  1. Definir uma variável merged_arr que conterá o resultado
  2. Inicialize um hash vazio e sem nome como intermediário para colocar elementos exclusivos em
  3. Use Object#tappara preencher o hash (referenciado como hashnotap bloco) e retorná-lo para o encadeamento subsequente do método
  4. Concatenar arr1earr2 em uma única matriz não processada
  5. Para cada elemento elna matriz concatenada, colocar o valor elem hash[el]caso nenhum valor de hash[el]existe actualmente. A memorização aqui (hash[el] ||= el ) é o que garante a exclusividade dos elementos.
  6. Busque as chaves (ou valores, pois são iguais) para o hash agora preenchido

Isso deve ser executado em O(n) tempo. Informe-me se fiz alguma declaração imprecisa ou se posso melhorar a resposta acima por questões de eficiência ou legibilidade.

Possíveis melhorias

O uso de memoização é provavelmente desnecessário, pois as chaves do hash serão únicas e os valores irrelevantes; portanto, isso é suficiente:

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

Eu realmente amo Object#tap, mas podemos alcançar o mesmo resultado usando Enumerable#reduce:

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

Você pode até usar Enumberable#map:

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

Como eu faria isso na prática

Dito tudo isso, se me pedissem para mesclar duas matrizes arr1e arr2que o resultado merged_arrtivesse elementos únicos e pudesse usar qualquer método Ruby à minha disposição, eu simplesmente usaria o operador de união de conjunto destinado a resolver esse problema exato:

merged_arr = arr1 | arr2

Uma rápida olhada na fonte de Array#|, no entanto, parece confirmar que o uso de um hash como intermediário parece ser a solução aceitável para executar uma mesclagem exclusiva entre duas matrizes.

OI
fonte
"Não use funções de matriz da biblioteca padrão para detectar singularidade (embora outras coisas formam a biblioteca padrão está bem)"
John Dvorak
Como estou violando essa regra no segundo exemplo? A memorização está sendo executada em um hash. Isso também não é permitido?
OI
2
Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Uma função que levaria n matrizes poderia ser a seguinte:

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

Jogando golfe, acho que isso deve 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)}

Atualizar Se você deseja manter o tipo original, pode

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
}

ou jogou golfe 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}

Isso ainda pode gerar algumas dúvidas, se você quiser distinguir 123e '123', então, isso não funcionaria ..

Konijn
fonte
Obrigado pela resposta. É impressionantemente curto, no entanto, isso representa apenas metade do problema. Você também precisa incluir na solução a peça de mesclagem real (mesmo que seja a mesma do exemplo original) e reunir tudo em uma única função. Além disso, você poderia fornecer a versão "golfed" além desta (como está O(N))?
Hck
Isso lança todos os membros em strings. por exemplo, m([1,2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7])torna["1", "2", "3", "4", "5", "6", "7"]
George Reith
2

python, 46

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

Ou, usando a operação definida simplesmente

python, 8

set(a+b)
Wasi
fonte
1
Desculpe, não estava claro, o uso de operações definidas também está trapaceando.
Hck
Seu primeiro código terá duplicatas se houver duplicatas em a ou se houver duplicatas em be esse elemento não estiver em a.
Vedant Kandoi
2

Perl

23 bytes, se contarmos apenas o bloco de código dentro da sub-rotina. Pode ser 21, se a substituição de valores globais for permitida (ela será removida mydo código). Ele retorna elementos em ordem aleatória, porque a ordem não importa. Quanto à complexidade, em média é O (N) (depende do número de colisões de hash, mas são bastante raras - na pior das hipóteses, pode ser O (N 2 ) (mas isso não deve acontecer, porque Perl pode detectar hashes patológicos e altera a semente da função hash quando detecta esse comportamento)).

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;

Saída (também mostrando aleatoriedade):

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

Fortran: 282 252 233 213

Versão Golfed:

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 não apenas parece infinitamente melhor, mas também compila (uma linha muito longa em sua forma de golfe) com a forma legível 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

Este deve ser O(n)como eu copiar apara ce, em seguida, verificar cada bcontra todosc . O último passo é eliminar o lixo que cconterá, pois não foi inicializado.

Kyle Kanos
fonte
2

Mathematica 10 Chars

Union[a,b]

Exemplo:

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

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

Mathematica2 43 Chars

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}
Murta
fonte
8
Eu acho que isso iria na categoria de usar métodos de matriz de biblioteca padrão.
Hck
Olá @ cloudcoder2000. Não há necessidade de chamar alguma biblioteca específica para usar o Union no Mathematica.
Murta
5
Na minha opinião, usar uma função interna para fazer exatamente o que a pergunta está pedindo é trapacear.
precisa saber é o seguinte
ok ok .. o segundo código não usa Union.
Murta
1
Eu acho Tally[Join[a, b]][[;; , 1]]que também seria trapaça ;-) BTW, você pode salvar caracteres usando variáveis ​​de letra única.
Yves Klett
1

Javascript 86

Versão Golfed:

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

Versão legível:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}
Bertrand
fonte
1
Isso ignora os valores falsey ... m([1,0,0,0,0],[0,1,0])retorna [1].
George Reith
1
Mude h[v]=vpara h[v]=1.
George Reith
Bem visto @GeorgeReith! Fomos 86-84 :)
Bertrand
Ainda é 86, acho que você ficou confuso porque removeu 2 caracteres da versão legível, e não da versão golfe.
George Reith
1

JavaScript 60

Estou usando o gerador ES6.
O seguinte é testável usando o Traceur REPL do Google .

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

Se você está procurando uma implementação baseada em JavaScript que se baseie nos objetos subjacentes por trás da estrutura para ser eficiente, eu teria usado o Set. Geralmente em uma implementação, o objeto Set manipula inerentemente objetos exclusivos durante a inserção com algum tipo de indexação de pesquisa binária. Eu sei que em Java é umlog(n) pesquisa, usando pesquisa binária com base no fato de que nenhum conjunto pode conter um único objeto mais de uma vez.


Embora eu não tenha idéia se isso também é verdade para Javascript, algo tão simples quanto o seguinte snippet pode ser suficiente para um n*log(n) implementação:

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

Experimente online!


Se o snippet acima usar a = [1,2,3]eb = [1,2,3,4,5,6] seguida s=[1,2,3,4,5,6].

Se você conhece a complexidade da Set.add(Object)função em JavaScript, avise-me, a complexidade disso é n + n * f(O)onde f(O)está a complexidade s.add(O).

Urna de polvo mágico
fonte
0

APL (Dyalog Unicode) , O (N), 28 bytes

Função de infixo tácito anônimo.

(⊢(/⍨)⍳∘≢=⍳⍨),

Experimente online!

, concatenar os argumentos; EM)

() Aplique a seguinte função tácita anônima nisso; O (1)

   ⍳⍨ índices selfie (índices da primeira ocorrência de cada elemento em toda a matriz); EM)

  = compare elemento por elemento com; EM):

   ⍳∘≢ índices do comprimento da matriz; EM)

(/⍨) use isso para filtrar; EM):

   o argumento não modificado; O (1)

O (N + 1 + N + N + N + N + 1) = O (N)

Adão
fonte
-2

JavaScript, 131 caracteres

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))
deepak_pal
fonte
4
Bem-vindo ao PPCG! Diga-nos que idioma é esse e formate-o como código para melhor legibilidade. (Isso funciona recuando as linhas de código com quatro espaços). Também uma explicação de sua abordagem seria apreciada.
Laikoni 26/10
é apenas um código javascript.
deepak_pal
@techdeepak Você pode adicionar essas informações vitais à sua postagem, formatá-las adequadamente, adicionar realce de sintaxe e escrever um pouco mais sobre a complexidade do algoritmo, pois é algoritmo mais rápido . Tal como está, este post é de qualidade bastante baixa.
Jonathan Frech
-2

PHP em torno de 28 caracteres [deixando de fora as variáveis ​​de matriz de exemplo e variável de resultado].

$ array1 = array (1, 2, 3); $ array2 = array (3, 4, 5);

$ resultado = array_merge ($ array1, $ array2);

Endri
fonte
Da pergunta: Não use as funções de matriz da biblioteca padrão para detectar exclusividade ou mesclar conjuntos / matrizes . Além disso, este não é realmente remover duplicatas da matriz
Jo rei
Eu acho que você tenha esquecido esta linha importante da questão: " Não use funções de matriz da biblioteca padrão para detectar singularidade ou fusão conjuntos / matrizes "
Peter Taylor
Sim. Está correto. Obrigado por apontarem isso. Críticas humildemente aceitas.
Endri
@brincadeira. Você está absolutamente certo sobre "Não use as bibliotecas padrão ...". O resto está errado. Ele remove as duplicatas. php.net/manual/en/function.array-merge.php . Eu recomendo que você leia completamente a documentação do PHP. Tenho 100% de certeza de que faz o trabalho. Você só precisa ter cuidado com qual das matrizes você considera duplicadas. Felicidades.
Endri
1
Eu literalmente executei o código em sua submissão sem alterações e a saída tem duplicatas. Looks como você deve ler a documentação, ou seja, Se, no entanto, as matrizes contêm teclas numéricas, o valor mais tarde não irá substituir o valor original, mas será anexado
Jo rei