Tell inversjoner med modifisert flettesortering
Tell antallet inversjoner i en tabell – par der a[i] > a[j] og i < j – ved å telle inversjoner på tvers av splittet under flettingen.
Tell inversjoner med modifisert flettesortering er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er en inversjon?
En inversjon i et array er et indekspar (i, j) der i < j, men a[i] > a[j] — et større element står før et mindre element. I [3, 1, 2] er for eksempel inversjonene (3,1) og (3,2), altså 2 inversjoner. Et sortert array har 0 inversjoner. Et omvendt sortert array med n elementer har n(n-1)/2 inversjoner. Inversjonstelling måler hvor langt et array er fra å være sortert.
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]Naiv O(n²)-tilnærming
Brute force-metoden kontrollerer alle par (i, j) med i < j og teller dem der a[i] > a[j]. Dette bruker O(n²) tid og O(1) plass. For n = 10⁵ innebærer det 5 × 10⁹ sammenligninger — for tregt. D&C-tilnærmingen med en modifisert merge sort løser problemet på O(n log n). Den avgjørende innsikten er at inversjoner på tvers av delingene kan telles effektivt under flettetrinnet i merge sort.
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])) # 3Innsikten fra merge sort
Under en fletting av to sorterte halvdeler L og R, hvis vi velger elementet R[j] fremfor L[i] (fordi R[j] < L[i]), er alle gjenværende elementer i L fra og med indeks i også større enn R[j]. Dette skyldes at L er sortert. Hver gang vi henter fra høyre halvdel, teller vi len(L) - i inversjoner på tvers av halvdelene. Denne opptellingen er gratis — den skjer under den vanlige flettingen.
# 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')Implementering av modifisert merge sort
Endre merge sort slik at den returnerer både det sorterte arrayet og inversjonstallet. Totalt antall inversjoner = inversjoner i venstre halvdel + inversjoner i høyre halvdel + inversjoner på tvers av delingene som blir funnet under flettingen. Basistilfellet returnerer (ett element, 0 inversjoner). Merge-funksjonen teller inversjoner mens den fletter. Total tid: 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])) # 3Gjennomgang av algoritmen
Gå gjennom [2, 4, 1, 3]: Del opp i [2, 4] og [1, 3]. Sortering av venstre del: [2, 4] → sortert [2,4], 0 inversjoner. Sortering av høyre del: [1, 3] → sortert [1,3], 0 inversjoner. Flett [2,4] og [1,3]: ta 1 (count += 2 for 2>1 og 4>1), ta 2 (ingen opptelling), ta 3 (count += 1 for 4>3), ta 4. Inversjoner på tvers av delingene = 3. Totalt = 0+0+3 = 3. Kontroller: parene (2,1), (4,1), (4,3) = 3 inversjoner. ✓
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]))Hvorfor inversjoner på tvers av delingene telles riktig
Korrekthet: Et hvilket som helst inversjonspar (a[i], a[j]) der i < j tilhører nøyaktig én av tre kategorier: (1) Begge ligger i venstre halvdel — telles av det rekursive kallet for venstre halvdel. (2) Begge ligger i høyre halvdel — telles av det rekursive kallet for høyre halvdel. (3) Elementet i venstre halvdel > elementet i høyre halvdel — telles under flettingen som en inversjon på tvers av delingene. Kategoriene er gjensidig utelukkende og uttømmende, så ingen inversjon telles to ganger eller utelates. Dette partisjonsargumentet er det standardiserte D&C-beviset for korrekthet.
# 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!')Anvendelser av inversjonstelling
Inversjoner måler hvor sortert et array er. Anvendelser: (1) Rangkorrelasjon: Kendall tau-avstanden mellom to rangerte lister er antallet inversjoner. (2) Effektivitet for insertion sort: insertion sort utfører nøyaktig like mange bytter som antallet inversjoner. (3) Analyse av bubble sort: Hver gjennomgang av bubble sort reduserer antallet inversjoner; antallet nødvendige gjennomganger tilsvarer antallet inversjoner. (4) Løsbarhet for puslespill: Et 8-puzzle eller 15-puzzle kan løses hvis og bare hvis antallet inversjoner har en bestemt paritet.
# 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 disagreementRelatert: Count Smaller Numbers After Self
Count Smaller Numbers After Self (LeetCode 315) spør for hvert element hvor mange elementer til høyre for det som er mindre. Dette er en inversjonstelling per element. Det kan løses med den samme modifiserte merge sort-algoritmen, samtidig som det føres oversikt over hvilke opprinnelige indekser som telles. Alternativt kan De bruke et Binary Indexed Tree (Fenwick Tree) eller en merge sort med indekssporing. D&C-tilnærmingen bruker O(n log n) tid.
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) teller par (i, j) der i < j og nums[i] > 2 × nums[j]. Standard inversjonstelling bruker nums[i] > nums[j]. Her endres terskelen til 2 × nums[j]. Tilpass merge sort: tell på tvers av delingene før flettingen (bruk to pekere til å telle mens venstre halvdel fortsatt har gyldige elementer), og flett deretter som normalt. Totalt 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])) # 3Globalt inversjonstall kontra lokalt
Globale og lokale inversjoner (LeetCode 775): Gitt en permutasjon av 0..n-1 skal du avgjøre om antallet globale inversjoner (alle par i<j der a[i]>a[j]) er likt antallet lokale inversjoner (nabopar). Nøkkelinnsikten er at enhver lokal inversjon også er global, så globalt ≥ lokalt. De er like hvis og bare hvis det ikke finnes inversjoner mellom ikke-naboer – det vil si at ingen verdi ligger mer enn én posisjon fra sin sorterte indeks. Dette reduseres til å kontrollere abs(a[i] - i) ≤ 1 for alle 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]Oppsummering av kompleksiteten ved inversjonstelling
Oppsummering: Brute force-telling av inversjoner har kompleksiteten O(n²). Modifisert flettesortering oppnår O(n log n) ved å telle inversjoner på tvers av delingene under flettesteget. Den ekstra kostnaden er O(1) per sammenligning (ved å legge til len(left) - i), så den totale ekstra kostnaden er O(n) per flettenivå – det samme som for standard flettesortering. Plassforbruket er O(n) for hjelpearrayene. Dette er det klassiske eksempelet på å bruke D&C til å telle ordensstatistikk på lineær-logaritmisk tid.
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')Kort sjekk
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du at: inversjoner måler hvor usortert et array er, med brute force i O(n²) og D&C i O(n log n), den modifiserte flettesorteringen teller inversjoner på tvers av halvdelene ved å legge til len(left)-i hver gang et høyreelement velges foran et venstreelement, og korrektheten bygger på partisjoneringen: venstre–venstre-, høyre–høyre- og tverrgående inversjoner er gjensidig utelukkende og dekker til sammen alle inversjoner. Neste tema er Boyer-Moores stemmegivningsalgoritme for å finne majoritetselementet.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Tell inversjoner med modifisert flettesortering» gratis?
Ja – hele teksten i «Tell inversjoner med modifisert flettesortering» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Tell inversjoner med modifisert flettesortering»?
Tell antallet inversjoner i en tabell – par der a[i] > a[j] og i < j – ved å telle inversjoner på tvers av splittet under flettingen. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Tell inversjoner med modifisert flettesortering»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Mal for splitt og hersk
- Tell inversjoner med modifisert flettesortering
- Majoritetselement: Boyer-Moore-avstemning
- Medianen av to sorterte tabeller