İçeriğe geç

Yerinde olmayanları say

Kolay#sorting#pairwise-comparison~15 dk

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

Hedef zaman
O(n log n)
Hedef alan
O(n)

Kodda değil de fikirde mi takıldın? Sıralama temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case