Count Inversions

Q: Czym jest inwersja w tablicy?

Inwersja to para pozycji i < j , dla których nums[i] > nums[j] , czyli większa wartość znajduje się przed mniejszą. Posortowana lista ma 0 inwersji, a lista z różnymi wartościami w odwrotnej kolejności ma ich najwięcej: n(n-1)/2 . Liczba inwersji jest równa liczbie zamian sąsiednich elementów wykonywanych przez sortowanie bąbelkowe.

Q: Jaka jest złożoność czasowa liczenia inwersji za pomocą sortowania przez scalanie?

Czas O(n log n) i dodatkowa pamięć O(n) na bufor scalania. Na każdym z log n poziomów scalania przetwarzana jest każda wartość, co daje około 3 × 10^5 kroków dla 2 × 10^4 wartości. Pętla porównująca pary ma złożoność O(n²) .

ŚrednieSortowanie Rekurencja

+10

Mając listę liczb całkowitych nums, zwróć liczbę inwersji: par indeksów i < j, dla których nums[i] > nums[j], czyli większa wartość występuje przed mniejszą. Równe wartości nigdy nie tworzą inwersji, a posortowana lista nie zawiera żadnych inwersji.

Funkcja

countInversions(nums: integer-array) → integer

numsinteger-array: lista liczb całkowitych
Zwracainteger: liczba par i < j, dla których nums[i] > nums[j]

Ograniczenia

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Wynik wynosi co najwyżej n(n-1)/2 < 2 × 10⁸, więc mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [5, 3, 8, 1, 4]
Wyjście: 6
Wyjaśnienie: 5 jest przed 3, 1 i 4: 3 pary. 3 jest przed 1, a 8 przed 1 i 4: jeszcze 3. 1 i 4 są we właściwej kolejności, więc suma wynosi 6.

Pytanie dodatkowe

Co się zmieni, jeśli para będzie liczona tylko wtedy, gdy nums[i] > 2 × nums[j]? Czy sortowanie przez scalanie nadal może liczyć takie pary w czasie O(n log n)?

Rozwiązanie

Sprawdzenie każdej pary wymaga około n² / 2 porównań. Sortowanie przez scalanie zlicza pary zbiorczo: gdy podczas scalania umieszczana jest wartość z prawej połowy, każda wartość z lewej, która wciąż czeka, jest większa i znajdowała się przed nią. Jedno odejmowanie zlicza całą tę grupę, więc zliczanie nie wymaga niczego poza sortowaniem O(n log n).

Sprawdź każdą parę

Poprawne, ale nie kończy się na największych testach

Intuicja

Dla każdego indeksu i sprawdź każdy późniejszy indeks j i dodaj 1, gdy nums[i] > nums[j]. To jest definicja, a ścisłe porównanie pomija równe wartości.

Koszt to n(n-1)/2 porównań: prawie 2 × 10^8 dla 2 × 10^4 wartości, a podwojenie n sprawia, że koszt jest czterokrotnie większy.

Algorytm

Ustaw count = 0.
Dla każdego i od 0 do n-1 oraz każdego j od i + 1 do n-1 dodaj 1 do count, gdy nums[i] > nums[j].
Zwróć count.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Sortowanie przez scalanie z liczeniem podczas scalania

Intuicja

Podziel listę w połowie. Inwersja ma obie wartości w lewej połowie, obie w prawej połowie albo po jednej po każdej stronie. Rekurencyjne wywołanie dla każdej połowy zlicza dwa pierwsze rodzaje inwersji i sortuje tę połowę. Sortowanie przesuwa wartości tylko w obrębie połowy, więc każda wartość z lewej połowy nadal znajduje się przed każdą wartością z prawej połowy, a pary przechodzące między połowami pozostają bez zmian.

Podczas scalania, jeśli left[i] ≤ right[j], umieść left[i]: każda wartość z prawej połowy, która wciąż czeka, jest co najmniej równa right[j], więc nie tworzy inwersji. W przeciwnym razie right[j] jest mniejsze od left[i], a ponieważ lewa połowa jest posortowana, także od każdej wartości z lewej połowy, która wciąż czeka. Dodaj ich liczbę. Umieszczenie wartości z lewej połowy przy remisie sprawia, że równe wartości nie tworzą inwersji.

Dla [5, 3, 8, 1, 4] połówki zawierają odpowiednio 1 i 2 inwersje. Podczas scalania [3, 5] z [1, 4, 8] wartość 1 przechodzi przed 3 i 5, a 4 przed 5: 1 + 2 + 3 = 6.

Algorytm

Skopiuj nums i utwórz bufor o tej samej długości.
Aby posortować i policzyć zakres zawierający mniej niż 2 wartości, zwróć 0.
W przeciwnym razie podziel go w miejscu mid, a następnie posortuj i policz każdą połowę.
Scal połowy za pomocą bufora: gdy left[i] ≤ right[j], wybierz wartość z lewej połowy; w przeciwnym razie wybierz wartość z prawej połowy i dodaj liczbę wartości z lewej połowy, które nie zostały jeszcze umieszczone.
Skopiuj scalony zakres z powrotem i zwróć sumę trzech zliczeń.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

Pułapki i przypadki brzegowe

Dodanie 1, gdy umieszczana jest wartość z prawej strony. Wyprzedza ona wszystkie wartości z lewej strony, które wciąż czekają, więc dodaj ich liczbę: mid - i.
Wybieranie wartości z prawej strony w przypadku remisu, przy użyciu left[i] < right[j] jako warunku wyboru strony lewej. Wtedy [2, 2, 2, 1] zlicza równe sobie 2 i zwraca wynik większy niż 3. Użyj ≤.
Zliczanie podczas kopiowania pozostałych wartości po wyczerpaniu jednej z połówek. Pozostałe wartości z lewej strony nie mają już po sobie żadnej wartości z prawej, a pozostałe wartości z prawej zostały już porównane z każdą wartością z lewej.

Najczęstsze pytania3

Czym jest inwersja w tablicy?

Inwersja to para pozycji i < j, dla których nums[i] > nums[j], czyli większa wartość znajduje się przed mniejszą. Posortowana lista ma 0 inwersji, a lista z różnymi wartościami w odwrotnej kolejności ma ich najwięcej: n(n-1)/2. Liczba inwersji jest równa liczbie zamian sąsiednich elementów wykonywanych przez sortowanie bąbelkowe.

Jaka jest złożoność czasowa liczenia inwersji za pomocą sortowania przez scalanie?

Czas O(n log n) i dodatkowa pamięć O(n) na bufor scalania. Na każdym z log n poziomów scalania przetwarzana jest każda wartość, co daje około 3 × 10^5 kroków dla 2 × 10^4 wartości. Pętla porównująca pary ma złożoność O(n²).

Czy można policzyć inwersje bez sortowania przez scalanie?

Tak. Drzewo Fenwicka (drzewo indeksowane binarnie) nad rangami wartości przechodzi przez listę jeden raz i dla każdej wartości sprawdza, ile wcześniejszych wartości jest większych, w czasie O(log n) na wartość. Łącznie daje to również O(n log n). Zrównoważone drzewo wyszukiwań, które śledzi rozmiary poddrzew, działa tak samo.

def countInversions(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [5, 3, 8, 1, 4]

Oczekiwany wynik