Conteggio delle inversioni con merge sort modificato
Conti il numero di inversioni in un array — coppie per cui a[i] > a[j] e i < j — contando le inversioni tra le due parti durante il passaggio di merge.
Conteggio delle inversioni con merge sort modificato è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è un'inversione
Un'inversione in un array è una coppia di indici (i, j) in cui i < j, ma a[i] > a[j]: un elemento più grande compare prima di uno più piccolo. Ad esempio, in [3, 1, 2], le inversioni sono (3,1) e (3,2), quindi ci sono 2 inversioni. Un array ordinato ha 0 inversioni. Un array di n elementi ordinato in senso inverso ha n(n-1)/2 inversioni. Il conteggio delle inversioni misura quanto un array è lontano dall'ordinamento.
arr = [3, 1, 2]
# Inversions: pairs (i,j) where i<j and arr[i]>arr[j]
inversions = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
inversions.append((arr[i], arr[j]))
print('Inversions in', arr, ':', inversions)
print('Count:', len(inversions)) # 2
# Maximum inversions in n-element array:
import math
n = 5
print(f'Max inversions for n={n}: {n*(n-1)//2}') # 10 for [5,4,3,2,1]Approccio ingenuo O(n²)
L'approccio a forza bruta controlla tutte le coppie (i, j) con i < j e conta quelle per cui a[i] > a[j]. Richiede tempo O(n²) e spazio O(1). Per n = 10⁵, ciò significa 5 × 10⁹ confronti: è troppo lento. L'approccio divide et impera basato su una versione modificata di merge sort risolve il problema in O(n log n). L'idea chiave è che durante la fase di merge di merge sort è possibile contare in modo efficiente le inversioni tra le due metà.
def count_inversions_brute(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_brute([3, 1, 2])) # 2
print(count_inversions_brute([5, 4, 3, 2, 1])) # 10
print(count_inversions_brute([1, 2, 3, 4, 5])) # 0
print(count_inversions_brute([2, 4, 1, 3, 5])) # 3L'intuizione alla base di merge sort
Durante il merge di due metà ordinate L e R, se scegliamo l'elemento R[j] invece di L[i] (perché R[j] < L[i]), allora tutti gli elementi rimanenti in L a partire dall'indice i sono anch'essi maggiori di R[j]. Questo perché L è ordinato. Pertanto, ogni volta che si preleva un elemento dalla metà destra, si contano len(L) - i inversioni tra le due metà. Questo conteggio è gratuito: avviene durante il normale merge.
# During merge of [1, 3, 5] and [2, 4, 6]:
# Compare L[0]=1 vs R[0]=2: take L[0]=1, no inversions
# Compare L[1]=3 vs R[0]=2: take R[0]=2, inversions += len(L)-1 = 2 (3>2, 5>2)
# Compare L[1]=3 vs R[1]=4: take L[1]=3, no inversions
# Compare L[2]=5 vs R[1]=4: take R[1]=4, inversions += len(L)-2 = 1 (5>4)
# Compare L[2]=5 vs R[2]=6: take L[2]=5, no inversions
# Take R[2]=6
# Total cross-inversions = 2 + 1 = 3
print('Cross-inversions identified during merge: 3')Implementazione di merge sort modificato
Modificare merge sort in modo che restituisca sia l'array ordinato sia il conteggio delle inversioni. Inversioni totali = inversioni della metà sinistra + inversioni della metà destra + inversioni tra le due metà individuate durante il merge. Il caso base restituisce (un singolo elemento, 0 inversioni). La funzione di merge conta le inversioni durante l'unione. Tempo totale: O(n log n).
def count_inversions(arr):
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_count = merge_sort_count(arr[:mid])
right, right_count = merge_sort_count(arr[mid:])
merged, cross_count = merge_count(left, right)
return merged, left_count + right_count + cross_count
def merge_count(left, right):
result, count = [], 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
count += len(left) - i # all remaining in left are inversions
result += left[i:] + right[j:]
return result, count
_, total = merge_sort_count(arr)
return total
print(count_inversions([3, 1, 2])) # 2
print(count_inversions([5, 4, 3, 2, 1])) # 10
print(count_inversions([2, 4, 1, 3, 5])) # 3Traccia dell'algoritmo
Traccia di [2, 4, 1, 3]: dividere in [2, 4] e [1, 3]. Ordinamento del sottoproblema sinistro: [2, 4] → ordinato [2,4], 0 inversioni. Ordinamento del sottoproblema destro: [1, 3] → ordinato [1,3], 0 inversioni. Unire [2,4] e [1,3]: prendere 1 (count += 2 per 2>1 e 4>1), prendere 2 (nessun conteggio), prendere 3 (count += 1 per 4>3), prendere 4. Inversioni tra le due metà = 3. Totale = 0+0+3 = 3. Verifica: coppie (2,1), (4,1), (4,3) = 3 inversioni. ✓
def count_with_trace(arr):
def ms(arr, depth=0):
indent = ' ' * depth
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = ms(arr[:mid], depth+1)
R, rc = ms(arr[mid:], depth+1)
merged, cc = merge_c(L, R)
print(f'{indent}merge({L},{R}) → cross={cc}')
return merged, lc + rc + cc
def merge_c(L, R):
res, c, i, j = [], 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]: res.append(L[i]); i += 1
else: res.append(R[j]); j += 1; c += len(L) - i
return res + L[i:] + R[j:], c
_, total = ms(arr)
return total
print('Total inversions:', count_with_trace([2, 4, 1, 3]))Perché le inversioni tra le due metà vengono conteggiate correttamente
Correttezza: ogni coppia di inversione (a[i], a[j]) con i < j appartiene esattamente a una di tre categorie: (1) entrambi gli elementi si trovano nella metà sinistra, conteggiati dalla chiamata ricorsiva sinistra. (2) Entrambi gli elementi si trovano nella metà destra, conteggiati dalla chiamata ricorsiva destra. (3) L'elemento della metà sinistra è > dell'elemento della metà destra, conteggiato durante il merge come inversione tra le due metà. Le categorie sono mutuamente esclusive ed esaustive, quindi nessuna inversione viene conteggiata due volte o tralasciata. Questo argomento di partizionamento è la dimostrazione standard della correttezza per D&C.
# Verification: compare with brute force on random arrays
import random
def count_brute(arr):
n = len(arr)
return sum(1 for i in range(n) for j in range(i+1,n) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a, 0
m=len(a)//2
L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr)[1]
for _ in range(100):
arr = random.choices(range(20), k=random.randint(1,10))
assert count_dc(arr[:]) == count_brute(arr), 'MISMATCH!'
print('All 100 random tests passed!')Applicazioni del conteggio delle inversioni
Le inversioni misurano il grado di ordinamento. Applicazioni: (1) Correlazione tra classifiche: la distanza tau di Kendall tra due liste ordinate è il numero di inversioni. (2) Efficienza di insertion sort: insertion sort esegue esattamente tanti scambi quante sono le inversioni. (3) Analisi di bubble sort: ogni passaggio di bubble sort riduce il numero di inversioni; il numero di passaggi necessari è uguale al numero di inversioni. (4) Risolubilità dei puzzle: un 8-puzzle o un 15-puzzle è risolvibile se e solo se il numero di inversioni ha una determinata parità.
# Kendall tau: number of inversions between two rankings
# Useful for comparing search result rankings or recommendation systems
def kendall_tau(rank1, rank2):
'''Count inversions where rank1 and rank2 disagree on relative order.'''
# Map rank2 positions to create a comparison sequence
pos = {v: i for i, v in enumerate(rank2)}
# Convert rank1 to position-in-rank2 ordering
arr = [pos[v] for v in rank1]
return count_inversions(arr)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
print(kendall_tau([1,2,3],[3,1,2])) # measures disagreementCorrelato: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) chiede, per ogni elemento, quanti elementi più piccoli si trovano alla sua destra. Si tratta di un conteggio delle inversioni per singolo elemento. Il problema può essere risolto con la stessa versione modificata di merge sort, tenendo traccia degli indici originali conteggiati. In alternativa, si può usare un Binary Indexed Tree (Fenwick Tree) oppure merge sort con tracciamento degli indici. L'approccio D&C richiede O(n log n).
def count_smaller(nums):
n = len(nums)
result = [0] * n
indexed = list(enumerate(nums))
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][1] <= right[j][1]:
# left[i] is placed; j elements from right are smaller and to the right
result[left[i][0]] += j
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
while i < len(left):
result[left[i][0]] += j # all of right is smaller
merged.append(left[i]); i += 1
return merged + right[j:]
merge_sort(indexed)
return result
print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]Reverse Pairs
Reverse Pairs (LeetCode 493) conta le coppie (i, j) in cui i < j e nums[i] > 2 × nums[j]. Il conteggio standard delle inversioni usa nums[i] > nums[j]. In questo caso, la soglia cambia in 2 × nums[j]. Si modifica merge sort contando le coppie tra le due metà prima del merge (usando due puntatori per contare finché nella metà sinistra rimangono elementi validi), quindi si esegue normalmente il merge. Tempo totale O(n log n).
def reverse_pairs(nums):
def merge_sort_count(arr):
if len(arr) <= 1: return arr, 0
mid = len(arr) // 2
L, lc = merge_sort_count(arr[:mid])
R, rc = merge_sort_count(arr[mid:])
# Count cross pairs: L[i] > 2*R[j]
j = 0
cross = 0
for l_val in L:
while j < len(R) and l_val > 2 * R[j]:
j += 1
cross += j
# Normal merge (separate from count)
merged = []
i = jj = 0
while i < len(L) and jj < len(R):
if L[i] <= R[jj]: merged.append(L[i]); i += 1
else: merged.append(R[jj]); jj += 1
merged += L[i:] + R[jj:]
return merged, lc + rc + cross
return merge_sort_count(nums)[1]
print(reverse_pairs([1, 3, 2, 3, 1])) # 2
print(reverse_pairs([2, 4, 3, 5, 1])) # 3Conteggio delle inversioni globali e locali
Inversioni globali e locali (LeetCode 775): data una permutazione di 0..n-1, determini se il numero di inversioni globali (tutte le coppie i<j con a[i]>a[j]) è uguale al numero di inversioni locali (coppie adiacenti). L'osservazione chiave è che ogni inversione locale è anche globale, quindi globale ≥ locale. Sono uguali se e solo se non ci sono inversioni tra elementi non adiacenti, ovvero nessun elemento si trova a più di 1 posizione dal proprio indice nell'array ordinato. Questo si riduce a verificare abs(a[i] - i) ≤ 1 per ogni i.
def is_ideal_permutation(A):
'''Global inversions == local inversions
iff no element is more than 1 position from its sorted index.'''
return all(abs(a - i) <= 1 for i, a in enumerate(A))
print(is_ideal_permutation([1, 0, 2])) # True
print(is_ideal_permutation([1, 2, 0])) # False (A[0]=1 is far from 2, A[2]=0 is far)
# Verification with inversion counts
print(count_inversions([1, 0, 2])) # 1 (global)
local1 = sum(1 for i in range(len([1,0,2])-1) if [1,0,2][i]>[1,0,2][i+1])
print('local:', local1) # 1 (equal)
def count_inversions(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2; L,lc=ms(a[:m]); R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]Riepilogo della complessità del conteggio delle inversioni
Riepilogo: il conteggio delle inversioni con la forza bruta è O(n²). Il merge sort modificato raggiunge O(n log n) contando le inversioni tra le due parti durante il merge. Il costo aggiuntivo è O(1) per confronto (aggiungendo len(left) - i), quindi il sovraccarico totale è O(n) per ogni livello di merge, come nel merge sort standard. Lo spazio occupato è O(n) per gli array ausiliari. Questo è l'esempio canonico dell'uso della tecnica divide et impera (D&C) per contare statistiche d'ordine in tempo lineare-logaritmico.
import time, random
def time_method(func, arr):
start = time.time()
result = func(arr[:])
return result, time.time() - start
def count_brute(arr):
return sum(1 for i in range(len(arr)) for j in range(i+1,len(arr)) if arr[i]>arr[j])
def count_dc(arr):
def ms(a):
if len(a)<=1: return a,0
m=len(a)//2;L,lc=ms(a[:m]);R,rc=ms(a[m:])
res,c,i,j=[],0,0,0
while i<len(L) and j<len(R):
if L[i]<=R[j]: res.append(L[i]);i+=1
else: res.append(R[j]);j+=1;c+=len(L)-i
return res+L[i:]+R[j:],(lc+rc+c)
return ms(arr[:])[1]
arr = random.sample(range(1000), 1000)
r1, t1 = time_method(count_brute, arr)
r2, t2 = time_method(count_dc, arr)
print(f'Brute: {r1} in {t1:.4f}s')
print(f'D&C: {r2} in {t2:.4f}s')
print(f'Speedup: {t1/t2:.1f}x')Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Strutture dati e algoritmi — Preparazione ai colloqui di programmazione trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: le inversioni misurano quanto un array è disordinato, con un approccio a forza bruta O(n²) e un approccio divide et impera O(n log n), il merge sort modificato conta le inversioni tra le due metà aggiungendo len(left)-i ogni volta che un elemento della parte destra viene scelto prima di un elemento della parte sinistra e la correttezza si basa sulla partizione: le inversioni nella parte sinistra, nella parte destra e tra le due parti sono mutuamente esclusive e insieme comprendono tutte le inversioni. Ora si analizzerà l'algoritmo di voto di Boyer-Moore per trovare l'elemento maggioritario.
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «Conteggio delle inversioni con merge sort modificato» è gratuita?
Sì — il testo completo di «Conteggio delle inversioni con merge sort modificato» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Conteggio delle inversioni con merge sort modificato»?
Conti il numero di inversioni in un array — coppie per cui a[i] > a[j] e i < j — contando le inversioni tra le due parti durante il passaggio di merge. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Conteggio delle inversioni con merge sort modificato»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema divide et impera
- Conteggio delle inversioni con merge sort modificato
- Elemento maggioritario: voto di Boyer-Moore
- Mediana di due array ordinati