Ich schaute auf die folgenden Frage von Glassdoor :
Bestimmen Sie, ob mehr als die Hälfte von N Credits Karten zur selben Person / Eigentümer gehören. Alles, was Sie haben, ist ein Array der Kreditkartennummern und ein API-Anruf wie isSamePerson (num1, num2).
Es ist klar, wie man es in O (n ^ 2) macht, aber einige Kommentatoren sagten, dass es in O (n) Zeit gemacht werden kann. Ist es überhaupt möglich? Ich meine, wenn wir eine Reihe von Kreditkartennummern haben, wo einige Nummern wiederholt werden, dann macht der Anspruch Sinn. Allerdings müssen wir für jede Kreditkartennummer einen API-Aufruf tätigen, um ihren Besitzer zu sehen.
Was fehlt mir hier?
Der Algorithmus läuft wie folgt ab:
Wenn es einen Großteil eines Gegenstandes (hier eine Person) gibt, dann wird dieser Gegenstand übrig bleiben, wenn Sie Gegenstände zusammenführen, die nicht gleich sind (in irgendeiner Reihenfolge).
Beachten Sie, dass dies nicht angewendet werden kann, wenn der Schwellenwert unter 50% liegt (aber es sollte möglich sein, sich an einen Schwellenwert von 33%, 25% ... anzupassen, indem Sie zwei, drei ... Kandidaten-Slots halten und nur einen Unterschied machen Dreibettzimmer, Vierbettzimmer ...).
Dies gilt auch für den Fall der Kreditkarten: Sie müssen nur zwei Elemente (Personen) für die Gleichheit (über den API-Aufruf) vergleichen und einen Zähler, der die Gesamtzahl der Elemente berücksichtigen kann.
Zeitkomplexität: O(N)
Raumkomplexität: O(1) + Eingabe
API-Aufrufe: bis zu 2N-1: Einmal in jedem Durchlauf ruft kein API das erste Element im ersten Durchlauf auf.
Sei x1, x2, ..., xn die Kreditkartennummer.
Beachten Sie, dass, da mehr als die Hälfte von ihnen zu derselben Person gehören, wenn Sie zwei benachbarte Zahlen berücksichtigen, mindestens ein Paar derselben Person gehören wird.
Wenn Sie alle Paare (x1, x2), (x3, x4) ... betrachten und die Teilmenge der Paare betrachten, in denen beide Elemente zu derselben Person gehören, gehört die Mehrheit der Paare derselben Person zur Person Wer hat die Mehrheit der Karten an erster Stelle. Also, behalten Sie für jedes Paar mit derselben Person eine der Kartennummern und für Paare, die nicht dieselbe Person sind, beide Karten ab. Führen Sie das rekursiv durch, und geben Sie das letzte verbleibende gleiche Personenpaar zurück.
Sie müssen höchstens n Vergleiche durchführen.
HINWEIS: Wenn n ungerade ist, behalten Sie die ungepaarte Zahl bei.
Warum das funktioniert: Betrachte einen Fall, in dem n gerade ist und Person A n / 2 + 1 Karten besitzt. Im schlimmsten Fall haben Sie genau ein Paar, in dem beide Karten A gehören. In diesem Fall gehört keines der anderen Paare derselben Person (andere Paare enthalten eine Karte von A und eine Karte von einer anderen Person).
Um nun ein passendes Paar B (Nicht-A-Person) zu erstellen, müssen Sie auch ein Paar B erstellen. Daher gehört zu jedem Zeitpunkt eine Mehrheit übereinstimmender Paare zu A.
Ich habe keinen guten Ruf. Die Methode von Jan Dvorak ist bekannt als Moores Voting-Algorithmus (Stream Counting Algorithm). Hier ist der Code.
%Vor%Die Frage ist, das Majoritätselement in einem Array herauszufinden. Ich werde verwenden Boyer-Moore Mehrheitswahl-Algorithmus. Ich mache das mit HashMap.
%Vor%Die Ausgabe ist 3.
DONE IN EINEM PASS:
Ich hoffe, dass dies verständlich ist und das Schreiben von Code eine einfache Sache ist.
ZEITKOMPLEXITÄT - O (N)
ANZAHL DER API-ANRUFE = N -1
RAUMKOMPLEXITÄT - O (1)
Tags und Links algorithm data-structures