Sortieren ist dein Freund.
Sortieren Sie die zwei Arrays (a und b), und gehen Sie dann (mit x und y als Zähler). Bewege beide um 1 nach unten. Von dort können Sie alle Ihre Tests ableiten:
(Ich habe vielleicht einen Randfall übersehen, aber Sie bekommen die allgemeine Idee.)
(Edit: Der Fall der primären Kante, der hier nicht behandelt wird, wird behandelt, wenn Sie das Ende eines der Arrays vor dem anderen erreichen, aber es ist nicht schwer herauszufinden.)
Sie könnten auch ein Dictionary<int, int> und einen ähnlichen Algorithmus verwenden:
Im endgültigen Wörterbuch erfahren Sie, welche Elemente (und wie oft) eingefügt / entfernt wurden. Diese Lösung sollte auch für größere Listen ziemlich schnell sein - schneller als das Sortieren.
Wenn Ihre Sprache als Multiset verfügbar ist (mit Anzahl von Elementen), ist Ihre Frage eine Standardoperation.
%Vor%Ergebnis ist A. symdiff (B) (symdiff ist Union minus Schnittpunkt und das ist genau das, was Sie gesucht haben, entfernt und hinzugefügt).
Offensichtlich können Sie auch nur entfernt werden oder nur unter Verwendung des klassischen Unterschieds zwischen den Sätzen hinzugefügt werden.
Es kann trivial mit Hashes implementiert werden und es ist O (n) (Verwendung von Sortierung ist etwas weniger effizient als es O (n.log (n)) wegen der Sortierung selbst).
Dies kann in linearer Zeit gelöst werden.
Erstellen Sie eine Karte zum Berechnen der Anzahl der Wiederholungen jedes Elements.
Gehe durch das before -Array und fülle die Karte.
Gehe durch das after -Array und verringere den Wert in der Map für jedes Element.
Am Ende, gehen Sie durch die Karte und wenn Sie einen negativen Wert finden, wurde dieses Element hinzugefügt - wenn positiv, wurde das Element entfernt.
Hier ist ein Java-Code dafür (nicht getestet, gerade geschrieben):
%Vor%In Groovy:
%Vor%Ergebnis:
%Vor% Für countBy wurde ich von Irgendein groovy magic post
In groovy inject ist wie reduce in anderen funktionalen Sprachen.
Ich beziehe mich auch auf Groovy Kollektion api Folien von Trygve Amundsen mit wirklich guter Tabelle mit funktionellen Methoden
Zweite Lösung:
%Vor%Tags und Links algorithm language-agnostic arrays