Überprüfen Sie, ob ein Array eine permutierte Version eines anderen Array ist

Question

ich, ob Array B überprüfen wollen, ist Permutation von Array A.

Ich dachte, es 1 verwendet getan werden kann for -loop, aber ich verschiedene Quellen sah, dass die meisten von ihnen hat mir gesagt, dass ich 2 for -loops verwenden soll.

for (int i = 0; i < A.length; i++) { 
    boolean found = false; 
    for (int j = 0; j < B.length; j++) 
     if (B[j] == A[i]) { 
      found = true; 
      break; 
     } 
     assert(found); 
    } 
    for (int i = 0; i < B.length; i++) { 
     boolean found = false; 
     for (int j = 0; j < A.length; j++) 
      if (A[j] == B[i]) { 
       found = true; 
       break; 
      } 
     assert(found); 
    } 

Ist dies eine korrekte Umsetzung mit 2 for -loops?

Übrigens, warum musste ich 2 for -loops durchführen, wo erste B mit A vergleicht, dann die zweite A mit B?

Answer 1

Ihr Code teilt die Permutation Prüfung in zwei Operationen:

1. für jedes Element A[i] überprüfen, ob A[i] in B
2. für jedes Element B[j] Prüfung wird angezeigt, wenn B[j] in A

Wie erscheint notiert von @Tom, funktioniert dies im allgemeinen Fall nicht, da es doppelte Elemente ignoriert.

Es ist auch ineffizient. Der zweite Teil kann weggelassen werden, wenn man vor allem anderen A.length == B.length überprüft, aber der Rest ist immer noch O(n²). Und es ist immer noch falsch, weil es falsch positive Ergebnisse liefert, wenn doppelte Elemente betrachtet werden.

Die --Mehr oder less-- kanonischen Verfahren ist sowohl einfach Art-Arrays und für Gleichheit vergleichen:

Arrays.sort(A); 
Arrays.sort(B); 
assert(Arrays.equals(A, B)); 

Sortierung ist wissen im Allgemeinen O(n ln n), so dass der gesamte Vorgang ist nun effizienter zu sein als Vor. Es macht auch die Dinge viel lesbarer.