Count Inversions
Bir tamsayı listesi nums verildiğinde, terslemelerin sayısını döndür: i < j ve nums[i] > nums[j] koşullarını sağlayan indeks çiftleri; yani daha küçük bir değerden önce gelen daha büyük bir değer. Eşit değerler hiçbir zaman tersleme oluşturmaz ve sıralı bir listede hiç tersleme yoktur.
Fonksiyon
- numsinteger-array
- tamsayıların listesi
- Döndürürinteger
- nums[i] > nums[j] koşulunu sağlayan i < j çiftlerinin sayısı
Kısıtlar
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Cevap en fazla
n(n-1)/2 < 2 × 108olur; bu nedenle işaretli 32 bitlik bir tam sayıya sığar.
Örnekler
- Girdi
- nums = [5, 3, 8, 1, 4]
- Çıktı
- 6
- Açıklama
- 5, 3, 1 ve 4’ten önce gelir: 3 çift. 3, 1’den; 8 ise 1 ve 4’ten önce gelir: 3 çift daha. 1 ve 4 sıralıdır, dolayısıyla toplam 6’dır.
- Girdi
- nums = [2, 2, 2, 1]
- Çıktı
- 3
- Açıklama
- Üç 2'nin her biri 1'den önce gelir, dolayısıyla 3 terslik vardır. Eşit olan iki 2 hiçbir zaman sayılmaz, çünkü bir terslik için önce kesinlikle daha büyük bir değer gerekir.
- Girdi
- nums = [-1, 0, 7, 7]
- Çıktı
- 0
- Açıklama
- Liste sıralanmıştır ve eşit olan iki 7 sayılmaz, bu nedenle cevap 0'dır.
Ek soru
Bir çift yalnızca nums[i] > 2 × nums[j] olduğunda sayılırsa ne değişir? Merge sort bu çiftleri hâlâ O(n log n) süresinde sayabilir mi?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Listeyi sol yarı ve sağ yarı olarak ayırın. Her terslik sol yarının içinde, sağ yarının içinde ya da her iki taraftan birer değer içeren bir çifttir. Üç grubu ayrı ayrı sayabilir misiniz?
Her yarıyı sıralamak, orta noktayı aşan çiftlerin sayısını değiştirmez; çünkü her sol değer, her sağ değerin solunda kalır. Her iki yarı da sıralandığında, orta noktayı aşan çiftleri tek tek saymak yerine gruplar hâlinde sayabilirsin.
Birleştirmeli sıralama kullanın. Sıralanmış iki yarıyı birleştirirken, sağ yarıdan her değer aldığınızda bu değer, sol yarıda hâlâ bekleyen tüm değerlerden küçüktür; bu nedenle orada kalan değerlerin sayısını ekleyin. Eşitlik durumunda sol yarıdan alın; böylece eşit değerler hiçbir zaman sayılmaz.
Çözüm
Her çifti kontrol etmek yaklaşık n² / 2 karşılaştırma alır. Birleştirme sıralaması, çiftleri toplu olarak sayar: birleştirme sırasında sağ yarıdan bir değer yerleştirildiğinde, hâlâ bekleyen her sol değer daha büyüktür ve ondan önce gelmiştir. Tek bir çıkarma bu grubun tamamını sayar; böylece sayma işlemi, O(n log n) sıralamasına ek bir maliyet getirmez.
Her çifti kontrol et
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her i indeksi için, sonraki her j indeksini kontrol edin ve nums[i] > nums[j] olduğunda 1 ekleyin. Tanım budur ve katı karşılaştırma eşit değerleri dışarıda bırakır.
Maliyet n(n-1)/2 karşılaştırmadır: 2 × 10^4 değer için yaklaşık 2 × 10^8; n değerini iki katına çıkarmak bunu dört katına çıkarır.
Algoritma
count = 0olarak ayarla.- 0'dan
n-1'e kadar herivei + 1'denn-1'e kadar herjiçin,nums[i] > nums[j]olduğundacount'u 1 artır. count'u döndür.
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 countBirleştirme sırasında sayım yapan birleştirme sıralaması
Sezgi
Listeyi ortadan ikiye böl. Bir terslikte her iki değer de sol yarıda, her iki değer de sağ yarıda ya da değerlerden biri her iki taraftadır. Her yarıda özyinelemeli olarak işlem yapmak ilk iki türü sayar ve o yarıyı sıralar. Sıralama değerleri yalnızca kendi yarılarında hareket ettirir; bu nedenle her sol değer hâlâ her sağ değerden önce gelir ve iki yarıyı aşan çiftler değişmez.
Birleştirme sırasında, left[i] ≤ right[j] ise left[i] değerini yerleştir: bekleyen her sağ değer en az right[j] kadar büyüktür, dolayısıyla terslik oluşturmaz. Aksi hâlde right[j], left[i] değerinden küçüktür ve sol yarı sıralı olduğundan, bekleyen her sol değerden de küçüktür. Bunların sayısını ekle. Eşitlik durumunda sol değeri yerleştirmek, eşit değerlerin terslik sayılmamasını sağlar.
[5, 3, 8, 1, 4] dizisinde yarılarda 1 ve 2 terslik vardır. [3, 5] ile [1, 4, 8] dizilerini birleştirirken 1, 3 ve 5'in önüne geçer; 4 ise 5'in önüne geçer: 1 + 2 + 3 = 6.
Algoritma
nums'u kopyalayın ve aynı uzunlukta bir arabellek oluşturun.- 2'den az değer içeren bir aralığı sıralayıp saymak için 0 döndürün.
- Aksi hâlde aralığı
midnoktasında bölün ve her yarıyı sıralayıp sayın. - Arabellek aracılığıyla yarıları birleştirin:
left[i] ≤ right[j]olduğunda sol değeri alın; aksi hâlde sağ değeri alın ve henüz yerleştirilmemiş sol değerlerin sayısını ekleyin. - Birleştirilmiş aralığı geri kopyalayın ve üç sayının toplamını döndürün.
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))
Tuzaklar ve uç durumlar
- Bir sağ değer yerleştirildiğinde 1 eklemek. Hâlâ bekleyen tüm sol değerleri geçer; bu yüzden sayılarını ekle:
mid - i. - Eşitlik durumunda sağ değeri almak ve sol taraf için test olarak
left[i] < right[j]kullanmak. Böylece[2, 2, 2, 1], eşit 2'leri birbirlerine karşı sayar ve 3'ten büyük bir sonuç döndürür.≤kullanın. - Yarımlardan biri tükendikten sonra kalanları kopyalarken saymak. Kalan sol değerlerden sonra hiçbir sağ değer gelmez; kalan sağ değerler ise tüm sol değerlerle zaten karşılaştırılmıştır.
Sıkça sorulan sorular3
Dizide tersine dönme nedir?
Tersine dönüş, i < j konumlarının nums[i] > nums[j] olduğu bir çifttir; yani daha büyük bir değer, daha küçük bir değerden önce gelir. Sıralı bir listede 0 tersine dönüş vardır; farklı değerlerden oluşan ters sıralı bir listede ise en fazla n(n-1)/2 tersine dönüş bulunur. Bu sayı, bubble sort'un yaptığı komşu eleman değişimlerinin sayısına eşittir.
Birleştirme sıralamasıyla terslikleri saymanın zaman karmaşıklığı nedir?
O(n log n) zaman ve birleştirme tamponu için O(n) ek alan. Birleştirmenin her log n düzeyi her değere bir kez dokunur; 2 × 10^4 değer için yaklaşık 3 × 10^5 adım gerekir. Çiftleri tek tek işleyen döngü O(n²) olur.
Ters sıralamalar, birleştirme sıralaması olmadan sayılabilir mi?
Evet. Değerlerin sıraları üzerinde bir Fenwick ağacı (ikili indeksli ağaç), listeyi bir kez dolaşır ve her değer için kendisinden önceki kaç değerin daha büyük olduğunu sorar; değer başına O(log n) sürede. Toplam süre de O(n log n) olur. Alt ağaç boyutlarını izleyen dengeli bir arama ağacı da aynı şekilde çalışır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def countInversions(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [5, 3, 8, 1, 4]
Beklenen Çıktı
6