Summary Ranges

Q: Wie hoch ist die Zeitkomplexität von Summary Ranges?

O(n) . Jeder Wert wird einmal besucht und jeder Bereich einmal geschrieben. Abgesehen von der Ausgabeliste beträgt der zusätzliche Speicherplatz O(1) : der Anfang des aktuellen Bereichs und ein oder zwei Indizes.

LeichtIntervalle Arrays und Strings

+10

Du erhältst ein sortiertes Array nums mit eindeutigen Ganzzahlen. Teile es in möglichst wenige Bereiche aufeinanderfolgender Ganzzahlen auf, sodass jeder Wert genau zu einem Bereich gehört. Gib einen Bereich a..b als Text "a->b" aus oder als "a", wenn er nur einen Wert enthält. Gib die Bereiche in aufsteigender Reihenfolge zurück.

Funktion

summaryRanges(nums: integer-array) → string-array

numsinteger-array: das sortierte Array unterschiedlicher Ganzzahlen
Gibt zurückstring-array: die Bereiche als Text, von den kleinsten bis zu den größten Werten

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums ist aufsteigend sortiert und enthält keine Duplikate.

Beispiele

Eingabe: nums = [0, 1, 2, 5, 6, 9]
Ausgabe: ["0->2", "5->6", "9"]
Erklärung: 0, 1, 2 folgen aufeinander und bilden daher "0->2". Der Sprung von 2 zu 5 beginnt einen neuen Bereich, "5->6", und 9 steht allein als "9".

Eingabe: nums = [-3, -1, 0, 1, 4, 7, 8]
Ausgabe: ["-3", "-1->1", "4", "7->8"]
Erklärung: -3 hat keinen Nachbarn (-2 fehlt), -1, 0, 1 bilden eine Folge, 4 steht allein, und 7, 8 schließen die Liste ab. Negative Werte funktionieren genauso: Auf -1 folgt -1 + 1 = 0.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, nums könnte Duplikate enthalten, zum Beispiel [1, 2, 2, 3]. Was würdest du ändern, damit weiterhin "1->3" ausgegeben wird?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Da die Werte sortiert und verschieden sind, ist ein Bereich aufeinanderfolgender Ganzzahlen immer eine Folge benachbarter Elemente im Array, und ein Bereich endet genau dort, wo sich zwei benachbarte Elemente um mehr als 1 unterscheiden. Teilt man das Array an jeder solchen Lücke, erhält man die kleinstmögliche Anzahl an Bereichen, da kein Bereich eine Lücke überqueren kann. Was bleibt, ist sorgfältige Buchführung: der Anfang jeder Folge, das letzte Element und das Textformat.

Prüfe beide Nachbarn jedes Werts

Idee

Betrachte jeweils einen Wert und stelle zwei Fragen. Beginnt hier ein Bereich? Ja, wenn dies der erste Wert ist oder der vorherige Wert nicht um eins kleiner ist. Endet hier ein Bereich? Ja, wenn dies der letzte Wert ist oder der nächste Wert nicht um eins größer ist.

In [0, 1, 2, 5, 6, 9] beginnt ein Bereich bei 0, 5 und 9 und endet bei 2, 6 und 9. Merke dir den Wert, bei dem der aktuelle Bereich begonnen hat. Wenn ein Bereich bei nums[i] endet, schreibe "start->nums[i]" oder nur "start", wenn der Bereich beim selben Wert begonnen und geendet hat, wie es bei 9 der Fall ist.

Jeder Wert wird einmal besucht und mit zwei Nachbarn verglichen, daher beträgt die Laufzeit O(n). Abgesehen von der Ausgabe merkst du dir einen Startwert, daher beträgt der zusätzliche Speicherbedarf O(1).

Algorithmus

Setze start = nums[0].
Für jeden Index i: Wenn i > 0 und nums[i] != nums[i-1] + 1, setze start = nums[i].
Wenn i der letzte Index ist oder nums[i+1] != nums[i] + 1, endet der Bereich hier.
Füge "start" hinzu, wenn start == nums[i], andernfalls "start->nums[i]".
Gib die Liste nach dem letzten Index zurück.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Zwei Zeiger für jeden zusammenhängenden Abschnitt

Idee

Betrachte jeden Bereich als einen Block des Arrays und finde seine beiden Enden. Der Zeiger i steht auf dem ersten Wert eines Bereichs. Der Zeiger j startet bei i und bewegt sich nach rechts, solange der nächste Wert genau um eins größer ist. Daher hält er beim letzten Wert des Bereichs an.

Für [-3, -1, 0, 1, 4, 7, 8]: i bei -3 kann den Bereich nicht erweitern, weil -1 nicht -2 ist. Der Bereich ist also "-3". Dann springt i zu -1, und j bewegt sich über 0 und 1 hinweg und hält vor 4 an: "-1->1". Dann folgen "4" und "7->8". Nach jedem Bereich bewegt sich i zu j+1, dem ersten Wert des nächsten Bereichs.

Die Bereiche sind so wenige wie möglich: Zwei Werte, die durch eine Lücke getrennt sind, können niemals zum selben Bereich gehören, und die Methode teilt nur an Lücken. Beide Zeiger bewegen sich nur vorwärts, daher läuft die innere Schleife über alle Bereiche hinweg insgesamt n Mal. Dadurch bleibt die Laufzeit bei O(n) und der zusätzliche Speicherbedarf bei O(1).

Algorithmus

Setze i = 0.
Setze j = i und bewege j nach rechts, solange j+1 < n und nums[j+1] == nums[j] + 1 gilt.
Füge "nums[i]" hinzu, wenn i == j, andernfalls "nums[i]->nums[j]".
Setze i = j + 1 und wiederhole den Vorgang, bis i das Ende überschreitet.
Gib die Liste zurück.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

Stolperfallen und Grenzfälle

Die Logik passt in wenige Zeilen; die Fehler liegen an den Rändern.

Den letzten Bereich vergessen. Eine Schleife, die einen Bereich nur dann schreibt, wenn sie auf eine Lücke trifft, schreibt daher nie den letzten, sodass [0, 1, 2, 5, 6, 9] sein "9" verliert. Schließe einen Bereich auch am letzten Index.
Für einen einzelnen Wert "a->a" schreiben. Ein Bereich mit nur einem Wert wird als "a" geschrieben.
Große Werte in wissenschaftlicher Notation ausgeben. R wandelt einen double wie 1000000000 in 1e+09 um; wandle die Werte in Ganzzahlen um, bevor du sie zusammenfügst.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Summary Ranges?

O(n). Jeder Wert wird einmal besucht und jeder Bereich einmal geschrieben. Abgesehen von der Ausgabeliste beträgt der zusätzliche Speicherplatz O(1): der Anfang des aktuellen Bereichs und ein oder zwei Indizes.

Warum ergibt das Schneiden an jeder Lücke die wenigsten Bereiche?

Ein Bereich enthält aufeinanderfolgende Ganzzahlen, daher kann er keine zwei Werte enthalten, zwischen denen eine Zahl fehlt. Jede Lücke im sortierten Array muss daher zwei Bereiche trennen, und bei g Lücken brauchst du mindestens g+1 Bereiche. Wenn du nur an den Lücken trennst, erhältst du genau g+1.

Wie gehst du mit einem Bereich um, der nur eine Zahl enthält?

Prüfe, ob der Bereich mit demselben Wert beginnt und endet. Wenn ja, gib nur diesen Wert an, wie "9". Wenn nicht, gib den Startwert, den Pfeil und den Endwert an, wie "5->6". Bei zwei Zeigern lautet die Prüfung i == j.

Muss die Eingabe für Summary Ranges sortiert sein?

Ja. Die Methode vergleicht nur Nachbarn und setzt daher voraus, dass aufeinanderfolgende Ganzzahlen nebeneinander liegen. Sortiere unsortierte Eingaben zuerst, wodurch die gesamte Aufgabe O(n log n) benötigt, oder speichere die Werte in einer Hash-Menge und erweitere jeden Bereich ausgehend von seinem kleinsten Wert, wie beim Problem der längsten Folge aufeinanderfolgender Zahlen.

Python

def summaryRanges(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums = [0, 1, 2, 5, 6, 9]

Erwartet

["0->2", "5->6", "9"]