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.
[1, 2, 2, 3]
e[2, 3, 4]
retornar[1, 2, 2, 3, 4]
ou[1, 2, 3, 4]
?Respostas:
Perl
27 caracteres
Simple Perl Hack
Tenho certeza de que alguém poderia dizer isso de uma só vez ... e assim (Obrigado Dom Hastings)
fonte
sub x{$_{$_}++for@_;keys%_}
(no caso de empate!) E usar como:z((1,2,3,4),(2,3,4,5,6))
JavaScript O (N)
13112411692 (86?)Versão Golfed:
Versão golfada legível humana:
eu poderia usar
concat
assim e fazê-lo em 86 caracteres: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):
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.
fonte
O(N)
.O(A*B)
( não está sendo usadoN
porque é confuso). Seria que se toda matriz de entrada (todaA
) tivesse a mesma quantidade de elementos (B
) que é atualmenteO(SUM(B) FOR ALL A)
, que pode ser reescrita comoO(N)
na definiçãoN
da contagem de elementos de todas as entradas da matriz.Python 2.7, 38 caracteres
Deve ser O (N) assumindo uma boa função de hash.
A
set
implementação de 8 caracteres de Wasi é melhor, se você não acha que isso viola as regras.fonte
PHP,
69/4268/41 caracteresA declaração da função inclui 68 caracteres:
A não inclusão da declaração da função possui 41 caracteres:
fonte
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.
Essencialmente, estas são as etapas que estou executando na linha acima.
merged_arr
que conterá o resultadoObject#tap
para preencher o hash (referenciado comohash
notap
bloco) e retorná-lo para o encadeamento subsequente do métodoarr1
earr2
em uma única matriz não processadael
na matriz concatenada, colocar o valorel
emhash[el]
caso nenhum valor dehash[el]
existe actualmente. A memorização aqui (hash[el] ||= el
) é o que garante a exclusividade dos elementos.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:
Eu realmente amo
Object#tap
, mas podemos alcançar o mesmo resultado usandoEnumerable#reduce
:Você pode até usar
Enumberable#map
:Como eu faria isso na prática
Dito tudo isso, se me pedissem para mesclar duas matrizes
arr1
earr2
que o resultadomerged_arr
tivesse 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: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.fonte
Uma função que levaria n matrizes poderia ser a seguinte:
Jogando golfe, acho que isso deve funcionar (117 caracteres)
Atualizar Se você deseja manter o tipo original, pode
ou jogou golfe 149:
Isso ainda pode gerar algumas dúvidas, se você quiser distinguir
123
e'123'
, então, isso não funcionaria ..fonte
O(N)
)?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"]
python, 46
Ou, usando a operação definida simplesmente
python, 8
fonte
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
my
do 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)).Saída (também mostrando aleatoriedade):
fonte
Fortran:
282252233213Versão Golfed:
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:
Este deve ser
O(n)
como eu copiara
parac
e, em seguida, verificar cadab
contra todosc
. O último passo é eliminar o lixo quec
conterá, pois não foi inicializado.fonte
Mathematica 10 Chars
Exemplo:
Mathematica2 43 Chars
fonte
Tally[Join[a, b]][[;; , 1]]
que também seria trapaça ;-) BTW, você pode salvar caracteres usando variáveis de letra única.Javascript 86
Versão Golfed:
Versão legível:
fonte
m([1,0,0,0,0],[0,1,0])
retorna[1]
.h[v]=v
parah[v]=1
.JavaScript 60
Estou usando o gerador ES6.
O seguinte é testável usando o Traceur REPL do Google .
fonte
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 é um
log(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
Experimente online!
Se o snippet acima usar
a = [1,2,3]
eb = [1,2,3,4,5,6]
seguidas=[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)
ondef(O)
está a complexidades.add(O)
.fonte
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)
fonte
JavaScript, 131 caracteres
fonte
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);
fonte