Tableaux brouillés – vérifiant si les éléments des tableaux correspondent (ordre importe peu) à la complexité O

J’essaie d’écrire du code qui prend deux tableaux, renvoie 1 si leurs éléments correspondent (l’ordre n’a pas d’importance) ou 0 s’ils ne correspondent pas.

  1. doit être sur)

J’ai écrit quelques algorithmes différents, un qui compare les sums des deux tableaux retournant 1 si elles sont identiques, 0 si elles ne le sont pas, mais si les tableaux contiennent des éléments de valeur différents qui totalisent la même chose, cela ne fonctionne pas. travail.

Trouver un O (n ^ 2) est simple (deux pour les boucles, comparer, puis itérer pour la position suivante de A, etc.

Je n’arrive pas à comprendre un O (n) qui fait cela. Le code actuel que j’ai prend la différence entre les valeurs et renvoie 1 si son 0. Ne sait toujours pas comment traiter les tableaux brouillés qui ne sont pas sortingés de la même manière. Y at-il un O (n) qui fait cela?

int scrambled( unsigned int a[], unsigned int b[], unsigned int len) { int count[100]; int flag = 1; int i; for(i=0; i<100; i++){ count[i] = 0; } for(i=0; i<len; i++){ count[a[i]]++; count[b[i]]--; } for(i=0; i<100; i++){ if(count[i] != 0){ return 0; } } return flag; 

Si vous pouvez utiliser C ++ 11, std::unordered_set peut être rempli en un temps O(n) , puis vous pouvez effectuer des tests d’appartenance à un élément O(n) (c’est toujours O(n) même si vous le faites deux fois; multiplicateurs constants ne compte pas).

Si C ++ 11 est sorti, vous pouvez toujours utiliser le même algorithme de base avec un ensemble de hachage écrit à la main, ou si les éléments de chacun se trouvent dans une plage liée, vous pouvez utiliser un sorting de comptage (qui est O(n+k) grâce à sa spécialisation pour les plages de nombres, si la plage est petite, la composante k importe peu).