Squares of a Sorted Array

Q: Jaka jest złożoność czasowa algorytmu „Squares of a Sorted Array”?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n) : każda wartość jest podnoszona do kwadratu i umieszczana raz. Podnoszenie do kwadratu, a następnie sortowanie kosztuje O(n log n) . Oba rozwiązania wymagają O(n) pamięci na wynik.

ŁatweDwa wskaźniki Sortowanie

+10

Otrzymujesz tablicę liczb całkowitych nums posortowaną w kolejności niemalejącej. Może zawierać wartości ujemne. Podnieś każdą wartość do kwadratu i zwróć kwadraty jako nową tablicę, również posortowaną w kolejności niemalejącej.

Funkcja

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: posortowana tablica liczb całkowitych, dopuszczalne są liczby ujemne
Zwracainteger-array: kwadrat każdej wartości, posortowane w kolejności niemalejącej

Ograniczenia

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums jest posortowane w kolejności niemalejącej.

Przykłady

Wejście: nums = [-6, -2, 1, 3, 7]
Wyjście: [1, 4, 9, 36, 49]
Wyjaśnienie: Kwadraty w pierwotnej kolejności to 36, 4, 1, 9 i 49. Wartości ujemne -6 i -2 dają duże kwadraty, więc sortowanie przesuwa 36 blisko końca: [1, 4, 9, 36, 49].

Wejście: nums = [-9, -4, -1]
Wyjście: [1, 16, 81]
Wyjaśnienie: Każda wartość jest ujemna, więc kwadraty wychodzą w odwrotnej kolejności: 81, 16, 1 daje [1, 16, 81].

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Podnoszenie do kwadratu i sortowanie zajmuje O(n log n). Czy potrafisz zrobić to w O(n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Podnoszenie do kwadratu zachowuje kolejność wartości nieujemnych, ale odwraca kolejność wartości ujemnych, więc kwadraty nie są posortowane. Ponowne sortowanie działa, ale ignoruje otrzymaną kolejność. Kluczowy fakt: największy kwadrat zawsze pochodzi z jednego z dwóch końców tablicy nums. Porównaj oba końce, umieść większy kwadrat na końcu wyniku i przesuwaj się do środka.

Podnieś do kwadratu, a następnie posortuj

Intuicja

Utwórz nową tablicę zawierającą kwadrat każdej wartości, a następnie ją posortuj. Kwadraty nigdy nie są ujemne, a sortowanie układa je w kolejności niezależnie od tego, skąd pochodzą.

Dla [-6, -2, 1, 3, 7] kwadraty to [36, 4, 1, 9, 49], a po sortowaniu otrzymujemy [1, 4, 9, 36, 49].

Sortowanie ma złożoność O(n log n). W tym przypadku jest wystarczająco szybkie, ale traktuje dane wejściowe tak, jakby nie miały żadnego porządku. Kolejne podejście wykorzystuje ten porządek i wymaga tylko jednego przebiegu.

Algorytm

Utwórz tablicę zawierającą x * x dla każdego x w nums.
Posortuj ją rosnąco według wartości liczbowych.
Zwróć ją.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Dwa wskaźniki z obu końców

Intuicja

Potraktuj liczby jako kwadraty odległości od 0. W posortowanej tablicy wartości najbardziej oddalone od 0 znajdują się na obu końcach: najbardziej ujemna po lewej, a najbardziej dodatnia po prawej. Dlatego największy kwadrat to nums[left]² lub nums[right]², nigdy żadna wartość pomiędzy nimi.

Pozostaw left na 0, a right na n-1 i wypełniaj wynik od ostatniej pozycji wstecz. W każdym kroku porównaj kwadraty obu wartości na końcach, wpisz większy z nich na bieżącej pozycji i przesuń odpowiedni wskaźnik do środka. To, co pozostaje między wskaźnikami, nadal jest posortowaną tablicą, więc ta sama zasada obowiązuje w każdym kroku.

Dla [-6, -2, 1, 3, 7]: 49 jest większe od 36 i trafia na koniec. Następnie 36 jest większe od 9, 9 od 4, 4 od 1, a 1 wypełnia pozycję 0. Wynik to [1, 4, 9, 36, 49]. Każda wartość jest umieszczana raz: czas O(n), a wynik jest jedyną dodatkową tablicą.

Algorytm

Utwórz tablicę wynikową o długości n. Ustaw left na 0, a right na n-1.
Przejdź po pozycjach pos od n-1 do 0.
Porównaj nums[left]² z nums[right]².
Wpisz większy kwadrat na pozycję pos i przesuń ten wskaźnik o jeden krok do środka.
Zwróć wynik.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Pułapki i przypadki brzegowe

Wersja z dwoma wskaźnikami jest krótka, ale kilka szczegółów może ją zepsuć.

Wypełnianie wyniku od początku. Najmniejszy kwadrat znajduje się tam, gdzie wartości przecinają 0, co może być w dowolnym miejscu pośrodku. Końce wskazują tylko największy kwadrat. Wypełniaj od końca.
Porównywanie nums[left] z nums[right] zamiast ich kwadratów lub wartości bezwzględnych. -6 jest mniejsze niż 3, ale jego kwadrat jest większy.
Zatrzymanie się, gdy left spotka się z right. Gdy są równe, jedna wartość wciąż nie została umieszczona; przejdź pętlą przez każdą pozycję wyniku albo użyj left <= right.
Dane wejściowe zawierające wyłącznie liczby ujemne albo wyłącznie dodatnie. Dla [-9, -4, -1] całą pracę wykonuje lewy wskaźnik, a dla [2, 5, 8] — prawy. W obu przypadkach wynik nadal musi być posortowany.
W JavaScript i TypeScript metoda sort() bez komparatora sortuje liczby jak tekst, więc [1, 4, 36, 9] zmienia się w [1, 36, 4, 9]. Przekaż (a, b) => a - b.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu „Squares of a Sorted Array”?

Rozwiązanie z dwoma wskaźnikami działa w czasie O(n): każda wartość jest podnoszona do kwadratu i umieszczana raz. Podnoszenie do kwadratu, a następnie sortowanie kosztuje O(n log n). Oba rozwiązania wymagają O(n) pamięci na wynik.

Dlaczego największy kwadrat powstaje z jednego z dwóch końców?

Kwadrat rośnie wraz z odległością od 0. W posortowanej tablicy wartość najbardziej oddalona od 0 po stronie liczb mniejszych od 0 jest pierwsza, a wartość najbardziej oddalona od 0 po stronie liczb większych od 0 jest ostatnia. Każda wartość pomiędzy nimi jest bliżej 0 niż jedna z nich, więc jej kwadrat nie może być największy.

Czy możesz wypełnić wynik od początku?

Tak, ale najpierw musisz znaleźć miejsce, w którym wartości przekraczają 0, na przykład za pomocą wyszukiwania binarnego. Następnie dwa wskaźniki przesuwają się na zewnątrz od tego miejsca, podobnie jak przy scalaniu dwóch posortowanych list: wartości ujemne odczytuje się od prawej do lewej, a nieujemne od lewej do prawej. Wypełnianie od końca pozwala uniknąć wyszukiwania, ponieważ końce są znane od początku.

Czy „Squares of a Sorted Array” to problem scalania?

Tak, po przekształceniu. Kwadraty wartości ujemnych tworzą jedną posortowaną listę (czytaną od prawej do lewej), a kwadraty wartości nieujemnych tworzą drugą. Połączenie ich to etap scalania w sortowaniu przez scalanie, dlatego wystarczy jedno liniowe przejście.

Python

def sortedSquares(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

nums = [-6, -2, 1, 3, 7]

Oczekiwane

[1, 4, 9, 36, 49]