J'ai récemment vu ce code Javascript sur StackOverflow pour fusionner deux tableaux et supprimer les doublons:

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

Bien que ce code fonctionne, il est horriblement inefficace ( O(n^2)). Votre défi est de créer un algorithme avec moins de complexité.

Le critère gagnant est la solution la moins complexe , mais les liens seront rompus par la plus courte longueur de caractères.

Prérequis :

Empaquetez tout votre code ensemble dans une fonction qui répond aux exigences suivantes de «correction»:

• Entrée: deux tableaux
• Sortie: un tableau
• Fusionne les éléments des deux tableaux ensemble - Tout élément dans l'un ou l'autre tableau d'entrée doit être dans le tableau en sortie.
• Le tableau en sortie ne doit pas avoir de doublons.
• L'ordre n'a pas d'importance (contrairement à l'original)
• N'importe quelle langue compte
• N'utilisez pas les fonctions de tableau de la bibliothèque standard pour détecter l'unicité ou fusionner des ensembles / tableaux (bien que d'autres choses de la bibliothèque standard soient correctes). Permettez-moi de faire la distinction que la concaténation de tableaux est correcte, mais les fonctions qui font déjà tout ce qui précède ne le sont pas.

Perl

27 personnages

Simple Perl Hack

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

Je suis sûr que quelqu'un pourrait aller seul. Et donc (Merci Dom Hastings)

sub x{$_{$_}++for@_;keys%_}

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

Version golfée:

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}

Version golfée lisible par l'homme:

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
}

Je pourrais utiliser concatcomme ça et le faire en 86 caractères:

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

Mais je ne sais pas s'il est toujours O (N) basé sur ce JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping car la version concat est légèrement plus rapide avec des tableaux plus petits mais plus lente avec des baies plus grandes (Chrome 31 OSX).

En pratique, faites cela (le golf regorge de mauvaises pratiques):

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

Je ne suis pas doué pour la complexité informatique, mais je pense que c'est O(N) . J'adorerais si quelqu'un pouvait clarifier.

Edit: Voici une version qui prend n'importe quel nombre de tableaux et les fusionne.

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

Python 2.7, 38 caractères

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

Doit être O (N) en supposant une bonne fonction de hachage.

L' setimplémentation de 8 caractères de Wasi est meilleure, si vous ne pensez pas qu'elle viole les règles.

PHP, 69/42 68/41 caractères

La déclaration de fonction comprend 68 caractères:

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

La déclaration de fonction ne comprend pas 41 caractères:

array_keys(array_flip($a)+array_flip($b))

Aller simple en Ruby

Pour respecter les règles décrites ci-dessus, j'utiliserais une stratégie similaire à la solution JavaScript et utiliserais un hachage comme intermédiaire.

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

Ce sont essentiellement les étapes que je traverse dans la ligne ci-dessus.

1. Définissez une variable merged_arrqui contiendra le résultat
2. Initialisez un hachage vide et sans nom comme intermédiaire pour mettre des éléments uniques dans
3. Utilisez Object#tappour remplir le hachage (référencé comme hashdans le tapbloc) et le renvoyer pour le chaînage de méthode ultérieur
4. Concaténation arr1et arr2en une seule matrice non traitée
5. Pour chaque élément eldans le tableau chaînés, mettre la valeur elen hash[el]si aucune valeur hash[el]existe actuellement. La mémorisation ici ( hash[el] ||= el) est ce qui garantit l'unicité des éléments.
6. Récupérez les clés (ou les valeurs, car elles sont identiques) pour le hachage maintenant rempli

Cela devrait fonctionner dans O(n) temps. Veuillez me faire savoir si j'ai fait des déclarations inexactes ou si je peux améliorer la réponse ci-dessus pour des raisons d'efficacité ou de lisibilité.

Améliorations possibles

L'utilisation de la mémorisation n'est probablement pas nécessaire étant donné que les clés du hachage seront uniques et que les valeurs ne sont pas pertinentes, donc cela suffit:

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

J'adore vraiment Object#tap, mais nous pouvons obtenir le même résultat en utilisant Enumerable#reduce:

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

Vous pourriez même utiliser Enumberable#map:

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

Comment je le ferais dans la pratique

Cela dit, si on me demandait de fusionner deux tableaux arr1et arr2que le résultat merged_arrait des éléments uniques et puisse utiliser n'importe quelle méthode Ruby à ma disposition, j'utiliserais simplement l'opérateur union défini qui est destiné à résoudre ce problème exact:

merged_arr = arr1 | arr2

Un coup d'œil rapide à la source de Array#|, cependant, semble confirmer que l'utilisation d'un hachage comme intermédiaire semble être la solution acceptable pour effectuer une fusion unique entre 2 tableaux.

Array.prototype.unique = function()
{
  var o = {},i = this.length
  while(i--)o[this[i]]=true
  return Object.keys(o)
}

Une fonction qui prendrait n tableaux pourrait être la suivante:

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

Golfé, je pense que cela devrait fonctionner (117 caractères)

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

Mise à jour Si vous souhaitez conserver le type d'origine, vous pouvez

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

Cela peut encore jeter des doutes, si vous voulez faire la distinction 123et '123'cela ne fonctionnera pas.

python, 46

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

Ou, en utilisant simplement l'opération set

python, 8

set(a+b)

Perl

23 octets, si l'on ne compte que le bloc de code à l'intérieur du sous-programme. Peut être 21, si l'écrasement des valeurs globales est autorisé (il serait supprimé mydu code). Il renvoie les éléments dans un ordre aléatoire, car l'ordre n'a pas d'importance. En ce qui concerne la complexité, en moyenne c'est O (N) (dépend du nombre de collisions de hachage, mais elles sont plutôt rares - dans le pire des cas, cela peut être O (N ² ) (mais cela ne devrait pas se produire, car Perl peut détecter les hachages pathologiques , et modifie la valeur de la fonction de hachage lorsqu'il détecte un tel comportement)).

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;

Sortie (montrant également le caractère aléatoire):

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

Fortran: 282 252 233 213

Version golfée:

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

Ce qui non seulement semble infiniment meilleur, mais se compilera en fait (une ligne trop longue dans sa forme jouée) avec la forme lisible par l'homme:

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

Cela devrait être O(n)comme je copie adans cpuis vérifie chacun bcontre tout c. La dernière étape consiste à éliminer les déchets qui ccontiendront car ils ne sont pas initialisés.

Mathematica 10 caractères

Union[a,b]

Exemple:

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

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

Mathematica2 43 caractères

Sort@Join[a, b] //. {a___, b_, b_, c___} :> {a, b, c}

Javascript 86

Version golfée:

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

Version lisible:

function merge(a, b) {
  var hash = {};
  return a.concat(b).filter(function (val) {
    return hash[val] ? 0 : hash[val] = 1;
  });
}

JavaScript 60

J'utilise le générateur ES6.
Les éléments suivants peuvent être testés à l'aide du Traceur REPL de Google .

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

Si vous recherchez une implémentation basée sur JavaScript qui s'appuie sur les objets sous-jacents derrière le framework pour être efficace, j'aurais juste utilisé Set. Habituellement, dans une implémentation, l'objet Set gère intrinsèquement des objets uniques lors de l'insertion avec une sorte d'indexation de recherche binaire. Je sais qu'en Java c'est unlog(n) recherche, utilisant une recherche binaire basée sur le fait qu'aucun ensemble ne peut contenir un seul objet plus d'une fois.

Bien que je ne sache pas si cela est également vrai pour Javascript, quelque chose d'aussi simple que l'extrait suivant peut suffire pour une n*log(n)implémentation:

JavaScript , 61 octets

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

Essayez-le en ligne!

Si l'extrait ci-dessus utilise a = [1,2,3]etb = [1,2,3,4,5,6] puis s=[1,2,3,4,5,6].

Si vous connaissez la complexité de la Set.add(Object)fonction en JavaScript, faites le moi savoir, la complexité de ceci est n + n * f(O)où f(O)est la complexité de s.add(O).

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

Fonction infixe tacite anonyme.

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

Essayez-le en ligne!

, concaténer les arguments; SUR)

(… ) Appliquer la fonction tacite anonyme suivante à ce sujet; O (1)

   ⍳⍨ indices selfie (indices de première occurrence de chaque élément dans l'ensemble du tableau); SUR)

  = comparer élément par élément à; SUR):

   ⍳∘≢ indices de la longueur du tableau; SUR)

 (/⍨) utilisez-le pour filtrer; SUR):

  ⊢ l'argument non modifié; O (1)

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

JavaScript, 131 caractères

var array1 = ["Vijendra","Singh"];   
var array2 = ["Singh", "Shakya"];     
result = Array.from(new Set([...array1, ...array2]))

PHP environ 28 caractères [en omettant les exemples de variables de tableau et la variable de résultat].

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

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