Was ist die Schnellste Möglichkeit, zu vergleichen, zwei arrays auf Gleichheit?

Ich habe zwei arrays von Objekten, die wahrscheinlich die gleichen Werte, aber in einer anderen Reihenfolge, z.B.

{ "cat", "dog", "mouse", "pangolin" }

{ "dog", "pangolin", "cat", "mouse" }

Möchte ich behandeln diese beiden arrays gleich. Was ist der Schnellste Weg, dies zu testen?

InformationsquelleAutor der Frage izb | 2010-11-11

  1. 18

    Kann ich nicht garantieren, dass dies die Schnellsteaber es ist sicherlich ziemlich effizient:

    bool areEquivalent = array1.Length == array2.Length 
                     && new HashSet<string>(array1).SetEquals(array2);

    BEARBEITEN:
    SaeedAlg und Sandris erhöhen gültigen Punkte über die verschiedenen Frequenzen von Dubletten verursachen Probleme mit diesem Ansatz. Ich sehe zwei Möglichkeiten, wenn dies wichtig ist (habe nicht viel daran gedacht, Ihre jeweiligen Wirkungsgrade):

    1.Sortieren Sie die Felder, und dann vergleichen Sie Sie der Reihe nach. Dieser Ansatz, in der Theorie, haben sollte quadratischen Komplexität im schlimmsten Fall.
    E. g.:

    return array1.Length == array2.Length
       && array1.OrderBy(s => s).SequenceEqual(array2.OrderBy(s => s));

    2.Der Aufbau eines Frequenz-Tabelle von Zeichenfolgen in jedem array und Sie dann vergleichen. E. g.:

    if(array1.Length != array2.Length)
   return false;

var f1 = array1.GroupBy(s => s)
               .Select(group => new {group.Key, Count = group.Count() });

var f2 = array2.GroupBy(s => s)
               .Select(group => new {group.Key, Count = group.Count() });

return !f1.Except(f2).Any();

    InformationsquelleAutor der Antwort Ani

  2. 4

    Ich denke, der einzige sinnvolle Weg ist, um Sie zu Sortieren und dann vergleichen.

    Sortierung erfordert O(n logn) und vergleichen O(n)so dass noch insgesamt O(n logn)

    InformationsquelleAutor der Antwort usr-local-ΕΨΗΕΛΩΝ

  3. 2

    Haben Sie versucht, so etwas wie

    string[] arr1 = {"cat", "dog", "mouse", "pangolin"};

string[] arr2 = {"dog", "pangolin", "cat", "mouse"};

bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0;

    InformationsquelleAutor der Antwort Adriaan Stander

  4. 1

    Konvertieren arrays zu HashSets und verwenden setequals

    InformationsquelleAutor der Antwort Martin DeMello

  5. 0

    Würde ich ein HashSet, vorausgesetzt, es gibt keine Duplikate

    string[] arr1 = new string[] { "cat", "dog", "mouse", "pangolin" };
string[] arr2 = new string[] { "dog", "pangolin", "cat", "mouse" };

bool result = true;
if (arr1.Length != arr2.Length)
{
    result = false;
}
else
{
    HashSet<string> hash1 = new HashSet<string>(arr1);
    foreach (var s in arr2)
    {
        if (!hash1.Contains(s))
            result = false;
    }
}

    Edit:

    Wenn Sie nur vier Elemente, könnte es schneller zu überspringen, HashSet und verwenden arr1.Enthält im Vergleich. Messen und wählen Sie die am schnellsten für Ihre array-Größe.

    InformationsquelleAutor der Antwort Albin Sunnanbo

  6. 0

    Pseudocode :

    A:array
B:array
C:hashtable

if A.length != B.length then return false;

foreach objA in A
{
H = objA;
if H is not found in C.Keys then
C.add(H as key,1 as initial value);
else
C.Val[H as key]++;
}

foreach objB in B
{
H = objB;
if H is not found in C.Keys then
return false;
else
C.Val[H as key]--;
}

if(C contains non-zero value)
return false;
else
return true;

    InformationsquelleAutor der Antwort Mohammad Mazaz

Schreibe einen Kommentar