Count Inversions
Diberikan sebuah list bilangan bulat nums, kembalikan jumlah inversi: pasangan indeks i < j dengan nums[i] > nums[j], yaitu nilai yang lebih besar berada sebelum nilai yang lebih kecil. Nilai yang sama tidak pernah membentuk inversi, dan list yang sudah terurut tidak memiliki inversi.
Fungsi
- numsinteger-array
- daftar bilangan bulat
- Mengembalikaninteger
- jumlah pasangan i < j dengan nums[i] > nums[j]
Batasan
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Jawabannya paling banyak
n(n-1)/2 < 2 × 108, jadi nilainya muat dalam bilangan bulat bertanda 32-bit.
Contoh
- Input
- nums = [5, 3, 8, 1, 4]
- Output
- 6
- Penjelasan
- 5 muncul sebelum 3, 1, dan 4: 3 pasangan. 3 muncul sebelum 1, dan 8 muncul sebelum 1 dan 4: 3 pasangan lagi. 1 dan 4 sudah berurutan, jadi totalnya 6.
- Input
- nums = [2, 2, 2, 1]
- Output
- 3
- Penjelasan
- Masing-masing dari tiga angka 2 muncul sebelum angka 1, jadi ada 3 inversi. Dua angka 2 yang sama tidak pernah dihitung, karena inversi mengharuskan nilai yang lebih besar muncul lebih dahulu.
- Input
- nums = [-1, 0, 7, 7]
- Output
- 0
- Penjelasan
- list sudah diurutkan, dan dua angka 7 yang sama tidak dihitung, jadi jawabannya 0.
Pertanyaan lanjutan
Apa yang berubah jika sepasang hanya dihitung ketika nums[i] > 2 × nums[j]? Apakah merge sort masih bisa menghitung pasangan tersebut dalam O(n log n)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Bagi list menjadi bagian kiri dan bagian kanan. Setiap inversi berada di dalam bagian kiri, di dalam bagian kanan, atau merupakan pasangan dengan satu nilai di setiap sisi. Bisakah kamu menghitung ketiga kelompok itu secara terpisah?
Mengurutkan setiap bagian tidak mengubah jumlah pasangan yang melewati bagian tengah, karena setiap nilai di bagian kiri tetap berada di sebelah kiri setiap nilai di bagian kanan. Setelah kedua bagian diurutkan, kamu bisa menghitung pasangan yang melewati bagian tengah secara berkelompok, bukan satu per satu.
Gunakan merge sort. Saat menggabungkan dua bagian yang sudah diurutkan, setiap kali kamu mengambil nilai dari bagian kanan, nilainya lebih kecil daripada setiap nilai yang masih menunggu di bagian kiri, jadi tambahkan jumlah nilai yang tersisa di sana. Jika nilainya sama, ambil dari bagian kiri agar nilai yang sama tidak pernah dihitung.
Solusi
Memeriksa setiap pasangan membutuhkan sekitar n² / 2 perbandingan. Merge sort menghitung pasangan sekaligus: saat nilai dari paruh kanan ditempatkan dalam proses merge, setiap nilai di kiri yang masih menunggu lebih besar dan muncul sebelumnya. Satu pengurangan menghitung seluruh kelompok itu, jadi penghitungan tidak menambah biaya di luar proses pengurutan O(n log n).
Periksa setiap pasangan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk setiap indeks i, periksa setiap indeks j setelahnya dan tambahkan 1 ketika nums[i] > nums[j]. Itulah definisinya, dan perbandingan ketat tidak menyertakan nilai yang sama.
Biayanya adalah n(n-1)/2 perbandingan: hampir 2 × 10^8 untuk 2 × 10^4 nilai, dan menggandakan n membuatnya empat kali lebih besar.
Algoritma
- Tetapkan
count = 0. - Untuk setiap
idari 0 hinggan-1, dan setiapjdarii + 1hinggan-1, tambahkan 1 kecountsaatnums[i] > nums[j]. - Kembalikan
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 countMerge sort yang menghitung saat menggabungkan
Intuisi
Bagi list menjadi dua di bagian tengah. Sebuah inversi memiliki kedua nilainya di bagian kiri, keduanya di bagian kanan, atau masing-masing satu di setiap sisi. Rekursi pada setiap bagian menghitung dua jenis pertama dan mengurutkan bagian tersebut. Pengurutan hanya memindahkan nilai di dalam satu bagian, sehingga setiap nilai di kiri tetap berada sebelum setiap nilai di kanan, dan pasangan yang melintasi kedua bagian tidak berubah.
Dalam penggabungan, jika left[i] ≤ right[j], tempatkan left[i]: setiap nilai di kanan yang masih menunggu setidaknya sebesar right[j], sehingga tidak membentuk inversi. Jika tidak, right[j] lebih kecil daripada left[i] dan, karena bagian kiri sudah terurut, lebih kecil daripada setiap nilai di kiri yang masih menunggu. Tambahkan jumlahnya. Menempatkan nilai dari kiri saat nilainya sama membuat nilai yang sama tidak dihitung sebagai inversi.
Pada [5, 3, 8, 1, 4], kedua bagian memiliki 1 dan 2 inversi. Saat menggabungkan [3, 5] dengan [1, 4, 8], 1 melewati 3 dan 5, lalu 4 melewati 5: 1 + 2 + 3 = 6.
Algoritma
- Salin
numsdan buat buffer dengan panjang yang sama. - Untuk mengurutkan dan menghitung rentang yang memiliki kurang dari 2 nilai, kembalikan 0.
- Jika tidak, bagi rentang pada
mid, lalu urutkan dan hitung masing-masing bagian. - Gabungkan kedua bagian melalui buffer: jika
left[i] ≤ right[j], ambil nilai dari kiri; jika tidak, ambil nilai dari kanan dan tambahkan jumlah nilai dari kiri yang belum ditempatkan. - Salin rentang yang telah digabungkan kembali, lalu kembalikan jumlah dari ketiga hitungan.
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))
Jebakan dan kasus tepi
- Menambahkan 1 saat nilai kanan ditempatkan. Nilai itu melewati semua nilai kiri yang masih menunggu, jadi tambahkan jumlahnya,
mid - i. - Mengambil nilai kanan jika nilainya sama, dengan
left[i] < right[j]sebagai pengujian untuk sisi kiri. Lalu[2, 2, 2, 1]menghitung nilai 2 yang sama satu sama lain dan menghasilkan nilai lebih dari 3. Gunakan≤. - Menghitung sambil menyalin nilai yang tersisa setelah salah satu bagian habis. Nilai kiri yang tersisa tidak memiliki nilai kanan setelahnya, dan nilai kanan yang tersisa sudah dibandingkan dengan setiap nilai kiri.
Pertanyaan yang sering diajukan3
Apa itu inversi dalam array?
Inversi adalah pasangan posisi i < j dengan nums[i] > nums[j], jadi nilai yang lebih besar berada sebelum nilai yang lebih kecil. list yang terurut memiliki 0 inversi, sedangkan list dengan nilai-nilai berbeda dalam urutan terbalik memiliki inversi terbanyak, yaitu n(n-1)/2. Jumlahnya sama dengan banyaknya pertukaran elemen yang bersebelahan yang dilakukan bubble sort.
Apa kompleksitas waktu untuk menghitung inversi dengan merge sort?
Waktu O(n log n) dan ruang tambahan O(n) untuk buffer merge. Setiap tingkat penggabungan dari log n menyentuh setiap nilai satu kali, sekitar 3 × 10^5 langkah untuk 2 × 10^4 nilai. Perulangan pasangan demi pasangan memiliki kompleksitas O(n²).
Apakah inversi bisa dihitung tanpa merge sort?
Ya. Pohon Fenwick (pohon berindeks biner) yang menggunakan peringkat nilai akan menelusuri list sekali dan, untuk setiap nilai, menghitung berapa banyak nilai sebelumnya yang lebih besar, dengan biaya O(log n) per nilai. Totalnya juga O(n log n). Pohon pencarian seimbang yang melacak ukuran subtree bekerja dengan cara yang sama.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def countInversions(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [5, 3, 8, 1, 4]
Output yang diharapkan
6