Wenn ich in Python eine Liste sortierter Ganzzahlen gebe, würde ich sie mit aufeinanderfolgenden Werten gruppieren und toleriere Lücken von 1.
Zum Beispiel bei einer Liste my_list :
Ich möchte die folgende Ausgabe:
%Vor%Nun, wenn ich Lücken von 1 nicht tolerieren müsste, könnte ich die saubere Lösung anwenden, erklärt hier :
%Vor%Gibt es eine Möglichkeit, meine zusätzliche Anforderung in die obige Lösung einzubauen? Wenn nicht, was ist der beste Weg, um das Problem anzugehen?
Numpy ist ein sehr nützliches Werkzeug und nicht sehr schwierig zu lernen.
Dieses Problem ist in O(n) mit einer einzigen Codezeile lösbar (außer Import, Daten und Konvertierung in Liste - wenn Sie es wirklich brauchen):
Noch wichtiger ist, dass der Code sehr schnell ist, wenn Sie im Gegensatz zu einer reinen Python-Lösung große Listen verarbeiten müssen
Eine O (nlogn) -Lösung (vorausgesetzt, dass die Eingabeliste nicht sortiert ist) besteht darin, zuerst die angegebene Liste zu sortieren, dann durch jeden Wert zu iterieren und eine neue Gruppe zu erstellen, wenn die Differenz zwischen dem aktuellen Wert und der Der vorherige Wert ist mindestens 3.
Demo
%Vor% Denken Sie daran, Groupby an sich ist ziemlich lahm. Die Stärke von itertools.groupby ist der Schlüssel. Für dieses spezielle Problem müssen Sie einen geeigneten Schlüssel mit Speicher erstellen (statusloser Schlüssel wird hier nicht funktionieren).
Implementierung
%Vor%Objekt
%Vor%Wie es funktioniert
Jedes Mal, wenn eine neue Unterliste erstellt werden soll ( curr - prev > threshold ), können Sie eine Markierung umschalten. Es gibt verschiedene Möglichkeiten, ein Flag umzuschalten:
flag = 1; flag *= -1 flag = [0, 1 ]; flag = flag[::-1] flag = 0; flag = 0 if flag else 1 Wähle, was immer dein Herz fordert
Dies erzeugt einen begleitenden Schlüssel zusammen mit Ihrer Liste
%Vor% Jetzt als itertools.groupby , gruppiert aufeinanderfolgende Elemente mit demselben Schlüssel, alle Elemente mit Schlüsseln mit aufeinanderfolgenden 0 s oder 1 s sind zusammen gruppiert
Und Ihr Endergebnis wäre
%Vor%Folgendes habe ich mir ausgedacht. Es gibt ein bisschen ausführliche Initialisierung, aber es erledigt den Job. =)
%Vor% Ich verwende generell zip , wenn ich mit aufeinander folgenden Elementen arbeiten möchte, und Sie können islice verwenden, um das Erstellen des Listenausschnitts zu vermeiden:
Beachten Sie, dass Sie in Python 2.x itertools.izip verwenden müssen, um zu vermeiden, die Liste der 2-Tupel (current, next_) zu erstellen.