Sayı dizisi
- Algoritmalar kursu
- Orta seviye
- Ders 14/80
- 4 dk
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.
Başlangıç kodu
def build_count(arr):
# Sayı dizisi kurÖrnek çözüm
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]))Beklenen çıktı
[0, 2, 1, 1]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Sıklık artırma
count[____] += 1count[arr[i]] += 1Açıklama: arr[i] doğru.
2 Sayı dizisi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Sayı dizisi |
Sıklık |
Birikimli |
Konum |
Geriye yerleştir |
Kararlı |
Maliyet |
O(n+k) |
3 Birikimli toplam ne işe yarar?
- Bellek azaltmak
- Hızı düşürmek
- Konum belirleme Doğru cevap
- Karşılaştırma
Açıklama: Konum belirleme