Compte tenu de 2 tableaux, renvoie des éléments qui ne sont pas inclus dans les deux tableaux

voix
0

J'ai eu une entrevue, et fait l'une des questions décrites ci-dessous:

Compte tenu de deux tableaux, s'il vous plaît calculer le résultat: obtenir l'union, puis retirer l'intersection de l'union. par exemple

int a[] = {1, 3, 4, 5, 7};
int b[] = {5, 3, 8, 10}; // didn't mention if has the same value.

result = {1,4,7,8,10}

Ceci est mon idée:

  1. Trier a, b.
  2. Vérifiez chaque élément de l' baide « recherche dichotomique » dans a. Si non trouvé, passer. Dans le cas contraire, supprimer cet élément à la fois a,b
  3. Résultat = éléments laissés dans a+ éléments restants dansb

Je sais qu'il est un algorithme moche, mais néanmoins il est mieux que rien. Y at-il une meilleure approche que celle-ci?

Créé 09/10/2014 à 04:43
source utilisateur
Dans d'autres langues...                            


3 réponses

voix
0

Une autre (le meilleur à mon avis) approche:

vous n'avez pas besoin d'une recherche à travers vos deux listes. vous pouvez simplement séquentiellement les travers eux:

  • sorte a et b
  • déclarer un jeu de résultats vide
  • prendre itérateurs aux deux listes et répétez les étapes suivantes:
    • si les valeurs itérateurs sont inégales:
      ajoutez le plus petit nombre au jeu de résultats et incrémenter l'itérateur appartenance
    • si les valeurs itérateurs sont égales:
      incrémenter les deux itérateurs sans ajouter quelque chose à l'ensemble de résultats
    • si l' on arrive en fin iterator:
      ajouter tous les éléments restants de l'autre jeu au résultat
Créé 09/10/2014 à 16:56
source utilisateur

voix
0

Une autre approche peut être:

  • joindre les deux listes
  • trier la liste jointe
  • marcher dans la liste jointe et supprimer complètement tous les éléments qui se produit plusieurs fois

cela a un inconvénient: il ne fonctionne pas si les listes d'entrée ont déjà doublets. Mais puisque nous parlons de jeux et la théorie des ensembles, je me attends aussi les entrées d'être ensembles dans le sens mathématique.

Créé 09/10/2014 à 16:46
source utilisateur

voix
0

Il existe de nombreuses approches à ce problème. une approche est:

1. construct hash-map using distinct array elements of array a with elements as keys and 1 is a value.
2. for every element,e in array b
   if e in hash-map
      set value of that key to 0
   else
     add e to result array.
3.add all keys from hash-map whose values 1 to result array.
Créé 09/10/2014 à 05:17
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more