Summary Ranges
Otrzymujesz posortowaną tablicę nums zawierającą różne liczby całkowite. Podziel ją na jak najmniej zakresów kolejnych liczb całkowitych, tak aby każda wartość należała dokładnie do jednego zakresu. Zapisz zakres a..b jako tekst "a->b" lub jako "a", jeśli zawiera jedną wartość. Zwróć zakresy w kolejności rosnącej.
Funkcja
- numsinteger-array
- posortowana tablica różnych liczb całkowitych
- Zwracastring-array
- zakresy jako tekst, od najmniejszych wartości do największych
Ograniczenia
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsjest posortowana w kolejności rosnącej i nie zawiera duplikatów.
Przykłady
- Wejście
- nums = [0, 1, 2, 5, 6, 9]
- Wyjście
- ["0->2", "5->6", "9"]
- Wyjaśnienie
0, 1, 2następują po sobie, więc tworzą"0->2". Przeskok z 2 do 5 rozpoczyna nowy zakres,"5->6", a 9 występuje samodzielnie jako"9".
- Wejście
- nums = [-3, -1, 0, 1, 4, 7, 8]
- Wyjście
- ["-3", "-1->1", "4", "7->8"]
- Wyjaśnienie
- -3 nie ma sąsiada (brakuje -2),
-1, 0, 1tworzą ciąg, 4 występuje samodzielnie, a7, 8zamykają listę. Wartości ujemne działają tak samo: po -1 następuje -1 + 1 = 0.
Pytanie dodatkowe
Załóżmy, że nums może zawierać powtarzające się wartości, na przykład [1, 2, 2, 3]. Co byś zmienił, aby nadal wypisywał "1->3"?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Tablica jest posortowana. Kiedy dwie sąsiadujące wartości należą do tego samego zakresu?
Należą do siebie wtedy i tylko wtedy, gdy
nums[i+1] == nums[i] + 1. Każda inna para sąsiadów oznacza koniec jednego zakresu i początek następnego.Zapamiętaj, gdzie zaczyna się bieżący zakres. Idź do przodu, dopóki następna wartość jest o jeden większa od bieżącej; gdy ciąg zostanie przerwany lub skończy się tablica, zapisz zakres od jego początku do bieżącej wartości i rozpocznij następny zakres od kolejnej wartości.
Rozwiązanie
Ponieważ wartości są posortowane i różne, zakres kolejnych liczb całkowitych zawsze tworzy ciąg sąsiadujących elementów tablicy, a zakres kończy się dokładnie tam, gdzie różnica między dwoma sąsiadującymi elementami jest większa niż 1. Podzielenie tablicy w każdym takim miejscu daje najmniejszą liczbę zakresów, ponieważ żaden zakres nie może obejmować przerwy. Pozostaje już tylko staranne śledzenie początku każdego ciągu, ostatniego elementu i formatu tekstu.
Sprawdź obu sąsiadów każdej wartości
Intuicja
Przyjrzyj się kolejno każdej wartości i zadaj sobie dwa pytania. Czy w tym miejscu zaczyna się zakres? Tak, jeśli jest to pierwsza wartość albo poprzednia wartość nie jest o jeden mniejsza. Czy w tym miejscu kończy się zakres? Tak, jeśli jest to ostatnia wartość albo następna wartość nie jest o jeden większa.
W [0, 1, 2, 5, 6, 9] zakres zaczyna się przy 0, 5 i 9, a kończy przy 2, 6 i 9. Zapamiętaj wartość, przy której zaczyna się bieżący zakres. Gdy zakres kończy się przy nums[i], zapisz "start->nums[i]" albo tylko "start", jeśli zakres zaczął się i zakończył przy tej samej wartości, tak jak w przypadku 9.
Każda wartość jest odwiedzana raz i sprawdza dwóch sąsiadów, więc czas działania wynosi O(n). Poza wynikiem przechowujesz jedną zapamiętaną wartość początkową, więc dodatkowa przestrzeń wynosi O(1).
Algorytm
- Ustaw
start = nums[0]. - Dla każdego indeksu
i: jeślii > 0inums[i] != nums[i-1] + 1, ustawstart = nums[i]. - Jeśli
ijest ostatnim indeksem lubnums[i+1] != nums[i] + 1, zakres kończy się tutaj. - Dodaj
"start", gdystart == nums[i], w przeciwnym razie"start->nums[i]". - Zwróć listę po ostatnim indeksie.
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 rangesDwa wskaźniki w każdym ciągu
Intuicja
Traktuj każdy zakres jako blok tablicy i znajdź jego oba końce. Wskaźnik i wskazuje pierwszą wartość zakresu. Wskaźnik j zaczyna od i i przesuwa się w prawo, dopóki następna wartość nie jest dokładnie o jeden większa, więc zatrzymuje się na ostatniej wartości zakresu.
Dla [-3, -1, 0, 1, 4, 7, 8]: i przy -3 nie może rozszerzyć zakresu, ponieważ -1 to nie -2, więc zakres to "-3". Następnie i przeskakuje do -1, a j przesuwa się przez 0 i 1, po czym zatrzymuje się przed 4: "-1->1". Potem "4" i "7->8". Po każdym zakresie i przesuwa się na j+1, czyli pierwszą wartość następnego zakresu.
Zakresów jest możliwie najmniej: dwie wartości oddzielone przerwą nigdy nie mogą należeć do tego samego zakresu, a ta metoda dzieli tylko w miejscach przerw. Oba wskaźniki przesuwają się wyłącznie do przodu, więc pętla wewnętrzna wykonuje się łącznie n razy we wszystkich zakresach, dzięki czemu złożoność czasowa wynosi O(n), a dodatkowe miejsce O(1).
Algorytm
- Ustaw
i = 0. - Ustaw
j = ii przesuwajjw prawo, dopókij+1 < ninums[j+1] == nums[j] + 1. - Dodaj
"nums[i]", gdyi == j, w przeciwnym razie"nums[i]->nums[j]". - Ustaw
i = j + 1i powtarzaj, ażiprzekroczy koniec. - Zwróć listę.
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
Pułapki i przypadki brzegowe
Logika mieści się w kilku wierszach; błędy kryją się na krańcach.
- Pomijanie ostatniego zakresu. Pętla, która zapisuje zakres tylko wtedy, gdy napotyka przerwę, nigdy nie zapisuje ostatniego zakresu, więc
[0, 1, 2, 5, 6, 9]traci swoje"9". Zamknij zakres również przy ostatnim indeksie. - Zapisywanie
"a->a"dla pojedynczej wartości. Zakres obejmujący jedną wartość zapisuje się jako"a". - Wyświetlanie dużych wartości w notacji naukowej. R zamienia liczbę typu double, taką jak
1000000000, na1e+09; przed wklejeniem przekonwertuj wartości na liczby całkowite.
Najczęstsze pytania3
Jaka jest złożoność czasowa Summary Ranges?
O(n). Każda wartość jest odwiedzana raz, a każdy zakres jest zapisywany raz. Poza listą wynikową dodatkowe zużycie pamięci wynosi O(1): początek bieżącego zakresu i jeden lub dwa indeksy.
Dlaczego cięcie przy każdej przerwie daje najmniej zakresów?
Zakres zawiera kolejne liczby całkowite, więc nie może zawierać dwóch wartości, między którymi brakuje liczby. Każda luka w posortowanej tablicy musi zatem oddzielać dwa zakresy, a przy g lukach potrzebujesz co najmniej g+1 zakresów. Cięcie tylko w miejscach luk daje dokładnie g+1.
Jak obsłużyć zakres zawierający tylko jedną liczbę?
Sprawdź, czy zakres zaczyna się i kończy na tej samej wartości. Jeśli tak, zapisz tylko tę wartość, na przykład "9". Jeśli nie, zapisz wartość początkową, strzałkę i wartość końcową, na przykład "5->6". W przypadku dwóch wskaźników warunek to i == j.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def summaryRanges(nums):
# Wpisz tutaj kodTest #1
Test #2
Argument
nums = [0, 1, 2, 5, 6, 9]
Oczekiwany wynik
["0->2", "5->6", "9"]