Yerinde olmayanları say
Görev tanımı
Problem
Öğrenciler bir sırada duruyor ve her biri bir boyla tarif ediliyor. En kısadan en uzuna dizilmeleri gerekiyordu. Orada durması gereken boydan farklı boyda bir öğrenci tutan konumları say. Eşit boylar birbirinin yerine geçebilir, bu yüzden doğru boyu tutan bir konum asla sayılmaz.
Örnekler
Input: heights = [1, 1, 4, 2, 1, 3]
Output: 3
Neden: doğru sıra 1 1 1 2 3 4 ve üç konum uyuşmuyor
Input: heights = [5, 4, 3, 2, 1]
Output: 4
Neden: yalnız ortadaki öğrenci tesadüfen zaten doğru duruyor
Input: heights = [1, 2, 3]
Output: 0
Neden: edge case: zaten doğru bir sırada yerinde olmayan bir şey yok
İpuçları
0 / 3
Soru sana verilen sırayı önce bulman gereken bir sırayla karşılaştırıyor; yani bir şey saymadan önce o ikinci sırayı üret.
Hedef sıra basitçe aynı boyların en kısadan en uzuna dizilmiş hali; yani girdinin sıralı bir kopyası tam olarak karşılaştırman gereken şey.
Boyların bir kopyasını sırala, sonra iki sırayı konum konum birlikte dolaş ve iki boyun farklı olduğu konumları say. Orijinali değil, her zaman kopyayı karşılaştır; yoksa karşılaştırma kontrol edilen şeyin kendisini yok eder.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Çözüm
Hedef sıra yalnızca sıralanmış girdidir; yani bütün iş o kopyayı üretip konum konum karşılaştırmaktır. Girdinin kendisi yerine bir kopyasını sıralamak önemli: yerinde sıralamak değerlendirilen sıranın üzerine yazardı ve sayı her zaman sıfır çıkardı. Öğrencileri değil boyları karşılaştırmak yeter, çünkü eşit boydaki iki öğrenci birbirinin yerine geçebilir ve doğru boyu tutan bir konum, orada kim durursa dursun doğrudur. Sıralama için zaman O(n log n), kopya için alan O(n).
def count_out_of_place(heights):
target = sorted(heights) # a COPY, so the original line survives
mismatches = 0
for standing, expected in zip(heights, target):
if standing != expected: # this position holds the wrong height
mismatches += 1
return mismatches
print(count_out_of_place([1, 1, 4, 2, 1, 3])) # -> 3
print(count_out_of_place([5, 4, 3, 2, 1])) # -> 4
print(count_out_of_place([1, 2, 3])) # -> 0Kodda değil de fikirde mi takıldın? Sıralama temelleri bunu anlatıyor.