Wenn das Array in aufsteigender Reihenfolge sortiert ist, ist das Problem einfach. Definieren Sie eine Range Struktur oder Klasse, die einen Anfang und ein Ende hat. Dann gehe durch das Array. Wenn das aktuelle Element um eins mehr als das vorherige Element ist, aktualisieren Sie Range.end , andernfalls erstellen Sie einen neuen Bereich mit diesem Element als Range.begin . Speichern Sie die Bereiche in einem dynamischen Array oder einer verknüpften Liste. Oder drucke sie einfach aus, während du gehst.

Wenn das Array nicht sortiert ist, sortieren Sie es zuerst.

Hier ist eine C # 3.0'y-Methode:

Punkte von Interesse:

• automatische Eigenschaften (public int Property {get; set;})
• unter Verwendung neuer Objektinitialisierer (neuer Bereich {Begin = xxx; ...}
• unter Verwendung von yield für faule Auswertung
• mit linq-Erweiterungsmethoden (First () und Skip ())

-

Prost, David

Hier ist eine Python-Implementierung, es sollte einfach genug sein,

Dies gibt aus:

Ich weiß, ich weiß, es ist kein Algorithmus , aber ich fand es schwieriger, es ohne Einrückungsprobleme zu erklären, als nur eine Lösung dafür zu implementieren.

Wenn das Array wie in Ihrem Beispiel sortiert ist, würde ich Buckets mit einem Minimum und einem Maximum definieren.

Initialisieren: Erstellen Sie einen Bucket mit einem Minimum und einem Maximum, die dem ersten Wert entsprechen.

Loop: Vergleichen Sie jeden Wert mit dem Maximum des aktuellen Buckets. Wenn es gleich oder 1 mehr als das aktuelle Maximum ist, aktualisieren Sie die max. Wenn es um mehr als 1 größer als der Höchstwert ist, speichern Sie den Bucket in einer Bucket-Liste und starten Sie einen neuen Bucket.

Am Ende haben Sie eine Reihe von Eimern mit jeweils einem Minimum und einem Maximum. Wenn das Min das gleiche wie das Maximum ist, drucken Sie eine einzelne Zahl (dh in Ihrem Beispiel würde der erste Eimer eine minimale und eine maximale 1 haben). Wenn sie unterschiedlich sind, drucken Sie als Bereich.

Beispiel Implementierung in Lisp:

Im Grunde erhältst du eine Liste von Dingen, wo jedes Ding hat (am tiefsten im Eimer, am höchsten im Eimer). Das sind deine Bereiche.

Wenn die Liste nicht bereits sortiert ist, sortieren Sie sie zuerst.

C (gcc)

Es ist ähnlich wie die Python-Version .

Beispiel:

Ausgabe:

Vorausgesetzt, die Liste ist geordnet, könnten Sie am Ende beginnen und das nächste weiter subtrahieren. Während der Unterschied 1 ist, sind Sie in einer Reichweite. Wenn nicht, starten Sie eine neue Reihe.

d. h.

16-15 = 1

15-14 = 1

14-12 = 2, der Bereich ist 16-14 - starten Sie einen neuen Bereich.

Hier ist meine Perl-Lösung. Könnte sauberer und schneller sein, aber es zeigt, wie es funktioniert:

Meine Lösung in Java 1.5 wäre:

welche Ausgaben:

Greetz, GHad

Ich glaube, dass die Mergeinfo-Eigenschaft, die in Version 1.5 in Subversion eingeführt wurde, ein Format hat, das dem entspricht, was Sie verlangen. Sie könnten also die Quelle von Subversion durchsehen, um herauszufinden, wie sie es macht . Ich würde mich wundern, wenn es anders ist als die anderen Vorschläge, die hier schon gepostet wurden.

Ich nehme an, das Array X () ist vorsortiert (und wenn nicht, sortiere das Array vorher).

Nun, so würde ich es machen.

Erstellen Sie einen einfachen Bereichstyp, der Anfangs- / Endbereichswerte enthält. Fügen Sie einen Konstruktor hinzu, der nur einen Wert annimmt, und legt start = end = value fest. Pflegen Sie einen Stapel von Bereichsobjekten, arbeiten Sie sich durch eine sortierte Kopie des Arrays, erweitern Sie den oberen Bereich oder fügen Sie einen neuen Bereich hinzu. Genauer gesagt, wenn der Wert im Array 1 + der Endwert für das Bereichsobjekt auf dem to des Stapels ist, den Endwert für diesen Bereich inkrementieren, wenn nicht, einen neuen Bereich schieben (mit start = end = Wert bei Index in Array) auf den Stapel.

Hier ist meine beste Aufnahme in Haskell.

Perl 6

Python (& gt; = 2.6)

Diese Version behandelt zusätzlich Duplikate und unsortierte Sequenzen.

Beispiel:

Ausgabe: