Ich arbeite mit Strings und habe ein Szenario, in dem ich feststellen muss, ob eine Zeichenfolge (normalerweise eine kleine & lt; 10 Zeichen) wiederholte Zeichen enthält.
%Vor%Ich kann den string.ToCharArray () durchlaufen und jeden Charakter gegen jedes andere Zeichen im char [] testen, aber ich habe das Gefühl, dass mir etwas offensichtlich fehlt ... vielleicht brauche ich nur Kaffee. Kann jemand helfen?
BEARBEITEN:
Die Zeichenfolge wird sortiert, daher ist die Reihenfolge nicht wichtig, also ABCDA = & gt; AABCD
Die Häufigkeit der Wiederholungen ist ebenfalls wichtig, also muss ich wissen, ob die Wiederholung ein Paar oder Triplett usw. ist.
Wenn die Zeichenfolge kurz ist, dann ist das Schleifen und Testen möglicherweise die einfachste und effizienteste Methode. Ich meine, Sie könnten einen Hash-Satz erstellen (in jeder Plattform, die Sie verwenden) und die Zeichen durchlaufen, scheitern, wenn der Charakter bereits im Satz ist und sie dem Satz hinzufügen - aber nur das wahrscheinlich einen Vorteil bieten, wenn die Saiten länger sind.
EDIT: Jetzt, da wir wissen, dass es sortiert ist, mquander's Antwort ist die beste IMO. Hier ist eine Implementierung:
%Vor%Eine kürzere Alternative, wenn es Ihnen nichts ausmacht, die Verwendung des Indexers zu wiederholen:
%Vor%EDIT: Okay, mit der "Frequenz" -Seite werde ich das Problem ein wenig umdrehen. Ich gehe immer noch davon aus, dass die Zeichenfolge sortiert ist. Was wir also wissen wollen, ist die Länge des längsten Laufs. Wenn keine Wiederholungen vorhanden sind, ist die längste Lauflänge 0 (für eine leere Zeichenfolge) oder 1 (für eine nicht leere Zeichenfolge). Andernfalls sind es 2 oder mehr.
Zuerst eine stringspezifische Version:
%Vor% Nun können wir dies auch als allgemeine Erweiterungsmethode für IEnumerable<T> :
Dann können Sie zum Beispiel "AABCD".LongestRun() aufrufen.
Wenn die Zeichenfolge sortiert ist, können Sie sich jedes Zeichen der Reihe nach merken und sicherstellen, dass das nächste Zeichen niemals mit dem letzten Zeichen identisch ist.
Anders als bei Strings mit weniger als zehn Zeichen ist es wahrscheinlich genauso schnell oder schneller als alle anderen Dinge, jedes Zeichen gegen den Rest zu testen. Ein Bit-Vektor, wie von einem anderen Kommentator vorgeschlagen, kann schneller sein (hilft, wenn Sie eine kleine Menge von zulässigen Zeichen haben.)
Bonus: Hier ist eine raffinierte LINQ-Lösung, um Jons Funktionalität zu implementieren:
%Vor%Also, OK, es ist nicht sehr schnell! Du hast ein Problem damit?!
: -)
Dies sagt Ihnen sehr schnell wenn eine Zeichenkette Duplikate enthält:
%Vor%Es prüft nur die Anzahl der einzelnen Zeichen gegenüber der ursprünglichen Länge. Wenn sie anders sind, haben Sie Duplikate ...
Bearbeiten: Ich schätze, das kümmert sich nicht um die Häufigkeit der Duplikate, die du in deinem Schnitt notiert hast ... aber einige andere Vorschläge hier sorgen bereits dafür, also werde ich es nicht tun poste den Code, wie ich eine Anzahl von ihnen bereits feststellst, gibt Ihnen eine einigermaßen elegante Lösung. Ich mag besonders die Implementierung von Joe mit LINQ-Erweiterungen.
Da Sie 3.5 verwenden, können Sie dies in einer LINQ-Abfrage tun:
%Vor%Für jedes Zeichen, das mehr als einmal in der Eingabe erscheint, erhalten Sie das Zeichen und die Anzahl der Vorkommen.
Aktualisieren Jetzt benötigen Sie ein Array von Zählern, um eine Zählung aufrechtzuerhalten.
Behalte ein Bit-Array, wobei ein Bit ein eindeutiges Zeichen darstellt. Schalten Sie das Bit ein, wenn Sie auf ein Zeichen stoßen, und führen Sie die Zeichenfolge einmal aus. Eine Zuordnung des Bit-Array-Index und des Zeichensatzes steht Ihnen frei. Brechen Sie, wenn Sie sehen, dass ein bestimmtes Bit bereits aktiviert ist.
(oder was auch immer das Äquivalent in der Syntax Ihrer Regex-Bibliothek ist)
Dies ist nicht die effizienteste Methode, da es wahrscheinlich auf jedes Zeichen in der Zeichenfolge zurückgeht und dann erneut vorwärts scannt. Und ich befürworte normalerweise keine regulären Ausdrücke. Aber wenn Sie die Kürze wünschen ...
Ich fing an, nach Informationen im Internet zu suchen und kam zu folgender Lösung.
%Vor%Ich hoffe, es hilft, ich hatte ein Vorstellungsgespräch, in dem der Interviewer mich gebeten hat, das zu lösen, und ich verstehe, dass es eine allgemeine Frage ist.
Wenn es keine Reihenfolge gibt, in der Sie arbeiten könnten, könnten Sie ein Wörterbuch verwenden, um die Anzahl zu halten:
%Vor%Die von Jon beschriebene Hash-Lösung ist wahrscheinlich die beste. Sie könnten ein HybridDictionary verwenden, da dies gut mit kleinen und großen Datensätzen funktioniert. Wo der Buchstabe der Schlüssel ist und der Wert die Frequenz ist. (Aktualisieren Sie die Häufigkeit jedes Mal, wenn das Hinzufügen fehlschlägt oder das HybridDictionary für .Contains (key) den Wert true zurückgibt)