Bütçenin altındaki çiftler
Görev tanımı
Problem
Bir mağaza ürün fiyatlarını listeliyor ve bir fiyat iadeden sonra negatif bile olabiliyor. Fiyatlarının toplamı bütçeden küçük (eşitse sayılmaz) olan iki farklı ürünün çiftlerini say. Farklı konumlardaki iki ürün, fiyatları eşit olsa bile ayrı bir çift oluşturur.
Örnekler
Input: prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Neden: (4, -2), (-2, 0), (-2, 3), (-2, 1) ve (0, 1)'in hepsinin toplamı 3'ten küçük
Input: prices = [2, 2, 2], budget = 5
Output: 3
Neden: 2'lerden ikisini seçmenin üç yolunun her biri 4 eder
Input: prices = [5], budget = 100
Output: 0
Neden: edge case: tek ürün çift oluşturamaz
İpuçları
0 / 3
İki iç içe döngü her çifti kontrol eder ve doğru yazması kolaydır. Ama karesel; yani on kat uzun bir liste yüz kat uzun sürer.
Fiyatların sırası cevabı değiştirmez, bu yüzden önce sıralamakta serbestsin. Sıralı bir listede kalan en küçük ve en büyük fiyat sığıyorsa bu sana aradaki fiyatlar hakkında ne söyler?
Sırala, sonra her uca bir pointer koy. İki fiyat bütçenin altına sığıyorsa sol fiyat sağ pointer'a kadarki her fiyatla eşleşir; o sayıyı ekle ve sol'u içe kaydır. Değilse sağ fiyat hâlâ mevcut her fiyat için çok büyüktür; sağ'ı içe kaydır.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Kısıtlar
- prices are integers and can be negative
Çözüm
Sıralamak tek bir karşılaştırmanın birçok çifti aynı anda halletmesini sağlar. Kalan en küçük fiyat artı kalan en büyük fiyat bütçenin altındaysa aradaki her fiyat da en küçükle sığar; bu yüzden o çiftlerin hepsi sayılır ve en küçük emekliye ayrılır. Toplam çok büyükse en büyük fiyat kalan hiçbir şeyle sığamaz ve bunun yerine o emekliye ayrılır. Her adım bir fiyatı emekliye ayırır, yani sıralamadan sonraki tarama doğrusaldır. Sıralama için zaman O(n log n), sıralı kopya için alan O(n).
def pairs_below(prices, budget):
p = sorted(prices)
left, right, count = 0, len(p) - 1, 0
while left < right:
if p[left] + p[right] < budget:
count += right - left # p[left] fits with every price up to right
left += 1
else:
right -= 1 # p[right] fits with nothing left
return count
print(pairs_below([4, -2, 0, 3, 1], 3)) # -> 5
print(pairs_below([2, 2, 2], 5)) # -> 3
print(pairs_below([5], 100)) # -> 0Kodda değil de fikirde mi takıldın? O(n²) ve iç içe döngüler bunu anlatıyor.