Wie überprüft man, ob zwei Arrays gleicher Größe die gleichen Werte in C haben? (Komplexität O (n))

Question

Edit: Die Werte der Elemente reichen von 0 bis 99 von 0 bis 99. Ist das überhaupt möglich? Ich habe versucht, den folgenden Code zu verwenden, aber es ist offensichtlich falsch:

#include <stdio.h> 

int scrambled(unsigned int a[], unsigned int b[], unsigned int len) { 
    if (len = 0) { 
     return 1; 
    } else { 
     int sumA, sumB, i; 
     for (i = 0; i < len; i++) { 
      sumA += a[i]; 
     } 
     for (i = 0; i < len; i++) { 
      sumB += b[i]; 
     } 
     if (sumA == sumB) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

ich davon aus, dass zwei Felder mit der gleichen Summe der Werte würden auch die gleichen Werte haben, aber dies ist nicht der Fall. {2,2} und {3,1} haben die gleiche Summe, aber nicht die gleichen Werte.

Gibt es eine Möglichkeit zu überprüfen, ob ein Array mit anderen Worten eine Permutation eines anderen mit linearer Komplexitätszeit ist?

Answer 1

Ja verwenden, Hash in C++:

#include <iostream> 
#include <unordered_set> 

bool isEqual(int a1[], int a2[], int len) { 
    using namespace std; 
    unordered_set<int> s1(a1, a1 + len); //O(n) 
    unordered_set<int> s2(a2, a2 + len); // O(n) 
    return s1 == s2; // O(n) 
} 

int main() { 
    using namespace std; 
    int a1[5] = {5,2,3,4,1}; 
    int a2[5] = {1,3,2,5,4}; 
    std::cout << isEqual(a1, a2, sizeof(a1)/sizeof(int)) << std::endl; 

    int a3[5] = {0,2,3,4,5}; 
    int a4[5] = {1,6,2,5,4}; 
    std::cout << isEqual(a3,a4, sizeof(a3)/sizeof(int)) << std::endl; 
    return 0; 
} 

bei gleichen Wert in den Daten vorhanden ist, Austausch unordered_set zu unordered_multiset

Zusätzlich: http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp

Komplexität proportional zu n ruft Operator == auf value_type ruft zum Prädikat durch key_eq zurückgekehrt, und Aufrufe an die Hasher durch hash_function zurückgegeben, im Durchschnitt Fall, proportional zu N2 im schlechtesten Fall, wo N ist die Größe des Behälters.

Mehr schnell Pläne: implementiert eine benutzerdefinierte Hash-Tabelle, um Ihre Daten nach. Zum Beispiel, was ist der Bereich Ihres Datensatzes? Wie viele Zahlen hast du in einem Array?

Answer 2

Ich spreche Englisch nicht und ich bin nicht professioneller Entwickler

Wette ich jetzt dieses Problem verstehen.

Ich denke, das Problem, das Sie reset 'Suma' nicht wissen, ist, 'SUMB' Variable

Suma und SUMB haben einen Müll Wert

Ich glaube, Sie tun, dass

int sumA = 0, sumB = 0, i; 

Answer 3

Wenn die Werte der Elemente im Array klein genug sind, können Sie ein Array von Nullen arr mit einer Größe halten, die dem Maximalwert in den Arrays entspricht. Dann können Sie für ein Array A die Elemente durchlaufen und das entsprechende Element in arr als 1 markieren. Dann für das andere Array B, das gleiche tun und prüfen, ob es irgendwelche Elemente in A gibt, die nicht in B sind.

#include <stdio.h> 
#define MAX 10000 
int arr[10000]; 
int scrambled(unsigned int a[], unsigned int b[], unsigned int len) 
{ 
    if (len=0) 
    { 
    return 1; 
    } 
    else 
    { 
     for (int i=0; i<len; i++) 
     { 
      arr[A[i]] = 1; 
     } 
     int same = 1; 
     for (int i=0; i<len; i++) 
     { 
      if(arr[B[i]] != 1) 
       same = 0; 
     } 
     if (same) 
     { 
      return 1; 
     } 
     else  
     { 
      return 0; 
     } 
    } 
} 

Answer 4

Wenn Sie die Felder ändern können, können Sie sie mit Radixsort sortieren und sie mit einer einfachen for Schleife vergleichen. Die Radix-Sortierung hat eine Zeitkomplexität von O (N * log (maxN)) wobei maxN der Maximalwert einer beliebigen Zahl in dem Array ist. Für eine Anordnung von unsigned int ist dieser maximale Wert eine Konstante, daher eine Zeitkomplexität von O (N).