Sayı dizisi

Değer aralığı için bir sayı dizisi kurmayı öğrenirsin.

Sayı dizisi

Sayı dizisi, her anahtarın sıklığını tutar. count[i], i değerinin dizide kaç kez geçtiğidir.

İlk olarak tüm count sıfırlanır (boyut k = max(arr)+1). Sonra her eleman için count[arr[i]] += 1 yapılır.

Bu adım O(n + k). Negatif değerler için min ile kaydırma uygulanır.

Birikimli toplam

Sayı dizisini birikimli toplama çevirirsek, count[i] artık i'den küçük veya eşit kaç eleman olduğunu verir. Bu, her elemanın sıralı dizideki konumunu belirler.

Birikimli toplam: count[i] += count[i-1], i 1'den k-1'e.

Bu adım kararlı sıralama için kritiktir; elemanlar geriye doğru yerleştirilir.

Uygulama Sayı dizisi kur

build_count(arr) yaz. 0..max(arr) aralığında sayı dizisi döndür. print(build_count([1, 3, 1, 2])) ile [0, 2, 1, 1] yazdır.

Örnek çözümü göster

def build_count(arr):
    # Sayı dizisi kur
    count = [0] * (max(arr) + 1)
    for x in arr:
        count[x] += 1
    return count
print(build_count([1, 3, 1, 2]))

Kendini test et

Sıklık artırma
```
count[____] += 1
```
Cevabı göster
```
count[arr[i]] += 1
```
Sayı dizisi: kavramları eşleştir

Sayı dizisi

Sıklık
Birikimli

Konum
Geriye yerleştir

Kararlı
Maliyet

O(n+k)
Birikimli toplam ne işe yarar?
- Bellek azaltmak
- Hızı düşürmek
- Konum belirleme
- Karşılaştırma
Cevabı göster

Konum belirleme — Konum belirleme

Sıradaki ders: Çıktı dizisi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler