BIT ile Terslikler
Sırası bozulmuş çiftleri verimli biçimde sayın.
BIT ile Terslikler, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Ters Sıralı Çift Nedir
Bir ters sıralı çift, a[i] > a[j] olacak şekilde i < j koşulunu sağlayan bir çifttir. Bu, sırası bozulmuş tek bir çifttir; bunları saymak, bir dizinin ne kadar sırasız olduğunu ölçer.
Ters Sıralı Çiftler Neden Önemli
Ters sıralı çiftlerin sayısı, bir kabarcık sıralamasının yapacağı takas sayısına eşittir. Yarışma soruları bu kavramı sıralama ve düzensizlik sorularının içinde gizler.
Naif Sayım Çok Yavaştır
Her çifti kontrol etmek O(n^2) zaman alır. n yaklaşık 100000 olduğunda bu, on milyar kontroldür ve zaman sınırını çok aşar. Daha akıllı bir yönteme ihtiyacımız var. 🐢
BIT Fikri
Soldan sağa ilerleyin ve şu soruyu sorun: daha önce gelen kaç öğe mevcut öğeden büyüktür? Fenwick ağacı ilerledikçe bu soruyu yanıtlar.
Sıklığa Göre Sayma
BIT, değerler üzerinde bir sıklık tablosu tutar. update(v, 1), v değerinin şimdiye kadar taramada görüldüğünü kaydeder.
update(v, 1)Büyük Değerler Sonek Oluşturur
v'den büyük önceki değerler, görülen öğe sayısından v'ye kadar olanların çıkarılmasıyla bulunur. i'inci öğede bu değer i eksi query(v) olur.
inv += i - query(v)Koordinat Sıkıştırma
Değerler büyük veya negatifse önce onları 1..n aralığındaki sıralara eşleyin. Bu sıkıştırma, sıralamayı değiştirmeden BIT'i küçük tutar.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Tam Tarama
Dizide dolaşın, her büyük değer sayısını toplama ekleyin ve ardından mevcut değeri ekleyin. Devam eden toplam, ters sıralı çiftlerin sayısıdır.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)n log n Zamanda Çalışır
Her öğe biri sorgu, diğeri güncelleme olmak üzere iki işlem başlatır ve ikisi de O(log n) zamanda çalışır. Tüm sayım O(n log n) zamanda tamamlanır. 🚀
Birleştirmeli Sıralama Kuzenidir
Birleştirmeli sıralama da birleştirme adımı sırasında O(n log n) zamanda ters sıralı çiftleri sayar. BIT sürümünün baskı altında yazılması genellikle daha kısadır.
Sayacın Taşmasına Dikkat Edin
Ters sıralı çiftlerin sayısı yaklaşık n kare bölü ikiye ulaşabilir; bu çok büyük bir sayıdır. Python tam sayıları sınırsızdır, ancak diğer dillerde 64 bitlik bir türe ihtiyacınız olur.
Hızlı Kontrol
Taramanın maliyetini ne kadar kavradığınızı sınayın.
Özet: Düzensizliği Sayma
Soldan sağa ilerleyip bir BIT'e daha önce kaç büyük değerin geldiğini sorarak ters sıralı çiftleri O(n log n) zamanda saydınız. Gerektiğinde değerleri sıkıştırın. ✅
Sıkça Sorulan Sorular
“BIT ile Terslikler” dersi ücretsiz mi?
Evet — “BIT ile Terslikler” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“BIT ile Terslikler” dersinde ne öğreneceğim?
Sırası bozulmuş çiftleri verimli biçimde sayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“BIT ile Terslikler” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Önek Toplamları için Fenwick Ağacı
- BIT ile Terslikler
- Segment Ağacı: Oluşturma ve Sorgulama
- Aralık Güncellemeleri için Tembel Yayılım