Count Inversions

Q: Che cos'è un'inversione in un array?

Un'inversione è una coppia di posizioni i < j in cui nums[i] > nums[j] , quindi un valore più grande si trova prima di uno più piccolo. Una lista ordinata ha 0 inversioni, mentre una lista invertita di valori distinti ne ha il numero massimo, n(n-1)/2 . Il conteggio equivale al numero di scambi tra elementi vicini effettuati dal bubble sort.

Q: Qual è la complessità temporale del conteggio delle inversioni con il merge sort?

O(n log n) di tempo e O(n) di spazio extra per il buffer di fusione. Ciascuno dei log n livelli di fusione tocca ogni valore una volta, per circa 3 × 10^5 passaggi con 2 × 10^4 valori. Il ciclo coppia per coppia è O(n²) .

MedioOrdinamento Ricorsione

+10

Data una lista di numeri interi nums, restituisci il numero di inversioni: coppie di indici i < j per cui nums[i] > nums[j], ovvero un valore maggiore prima di uno minore. I valori uguali non formano mai un’inversione e una lista ordinata non ne contiene.

Funzione

countInversions(nums: integer-array) → integer

numsinteger-array: l'elenco di interi
Restituisceinteger: il numero di coppie i < j con nums[i] > nums[j]

Vincoli

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
La risposta è al massimo n(n-1)/2 < 2 × 10⁸, quindi rientra in un intero con segno a 32 bit.

Esempi

Input: nums = [5, 3, 8, 1, 4]
Output: 6
Spiegazione: 5 viene prima di 3, 1 e 4: 3 coppie. 3 viene prima di 1, e 8 prima di 1 e 4: altre 3. 1 e 4 sono in ordine, quindi il totale è 6.

Per approfondire

Cosa cambia se una coppia viene conteggiata solo quando nums[i] > 2 × nums[j]? Il merge sort può ancora contare queste coppie in O(n log n)?

Soluzione

Controllare ogni coppia richiede circa n² / 2 confronti. Merge sort conta le coppie in blocco: quando, durante una fusione, viene inserito un valore della metà destra, tutti i valori della metà sinistra ancora in attesa sono più grandi e lo precedevano. Una sottrazione conta l’intero gruppo, quindi il conteggio non costa nulla oltre all’ordinamento O(n log n).

Controlla ogni coppia

Corretto, ma non termina sui test più grandi

Intuizione

Per ogni indice i, controlla ogni indice successivo j e aggiungi 1 quando nums[i] > nums[j]. Questa è la definizione, e il confronto stretto esclude i valori uguali.

Il costo è di n(n-1)/2 confronti: quasi 2 × 10^8 per 2 × 10^4 valori, e raddoppiare n lo quadruplica.

Algoritmo

Imposta count = 0.
Per ogni i da 0 a n-1 e ogni j da i + 1 a n-1, aggiungi 1 a count quando nums[i] > nums[j].
Restituisci 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

Ordinamento per fusione che conta durante la fusione

Intuizione

Dividi la lista a metà. Un’inversione ha entrambi i valori nella metà sinistra, entrambi nella metà destra oppure uno per lato. La ricorsione su ciascuna metà conta i primi due tipi e ordina quella metà. L’ordinamento sposta i valori solo all’interno di una metà, quindi ogni valore a sinistra continua a precedere ogni valore a destra e le coppie che attraversano le due metà rimangono invariate.

Durante la fusione, se left[i] ≤ right[j], posiziona left[i]: ogni valore a destra ancora in attesa è almeno pari a right[j], quindi non forma alcuna inversione. Altrimenti right[j] è minore di left[i] e, poiché la metà sinistra è ordinata, è minore di ogni valore a sinistra ancora in attesa. Aggiungi il loro numero. Posizionare il valore a sinistra in caso di parità mantiene esclusi i valori uguali.

In [5, 3, 8, 1, 4], le metà contengono 1 e 2 inversioni. Fondendo [3, 5] con [1, 4, 8], 1 precede 3 e 5, e 4 precede 5: 1 + 2 + 3 = 6.

Algoritmo

Copia nums e crea un buffer della stessa lunghezza.
Per ordinare e contare un intervallo con meno di 2 valori, restituisci 0.
Altrimenti, dividilo in corrispondenza di mid e ordina e conta ciascuna metà.
Unisci le metà tramite il buffer: se left[i] ≤ right[j], prendi il valore a sinistra; altrimenti prendi il valore a destra e aggiungi il numero di valori a sinistra non ancora inseriti.
Copia di nuovo l’intervallo unito e restituisci la somma dei tre conteggi.

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))

Trappole e casi limite

Aggiungere 1 quando viene inserito un valore di destra. Supera tutti i valori di sinistra ancora in attesa, quindi aggiungi il loro numero, mid - i.
Prendere il valore di destra in caso di parità, usando left[i] < right[j] come test per il lato sinistro. Così [2, 2, 2, 1] conta i valori 2 uguali tra loro e restituisce più di 3. Usa ≤.
Contare mentre si copiano i valori rimanenti dopo che una metà è esaurita. I valori di sinistra rimanenti non hanno valori di destra dopo di loro, e i valori di destra rimanenti sono già stati confrontati con ogni valore di sinistra.

Domande frequenti3

Che cos'è un'inversione in un array?

Un'inversione è una coppia di posizioni i < j in cui nums[i] > nums[j], quindi un valore più grande si trova prima di uno più piccolo. Una lista ordinata ha 0 inversioni, mentre una lista invertita di valori distinti ne ha il numero massimo, n(n-1)/2. Il conteggio equivale al numero di scambi tra elementi vicini effettuati dal bubble sort.

Qual è la complessità temporale del conteggio delle inversioni con il merge sort?

O(n log n) di tempo e O(n) di spazio extra per il buffer di fusione. Ciascuno dei log n livelli di fusione tocca ogni valore una volta, per circa 3 × 10^5 passaggi con 2 × 10^4 valori. Il ciclo coppia per coppia è O(n²).

Si possono contare le inversioni senza usare il merge sort?

Sì. Un albero di Fenwick (albero binario indicizzato) sui ranghi dei valori scorre l’elenco una volta e, per ogni valore, chiede quanti valori precedenti sono più grandi, in O(log n) per valore. Anche il totale è O(n log n). Un albero di ricerca bilanciato che tiene traccia delle dimensioni dei sottoalberi funziona allo stesso modo.

def countInversions(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso