Selamlar, haftanın soru ve çözümü ile geldik.
Soru: Find the Median 🦧
Sırasız bir şekilde verilen listenin medianını bulmamız ve bulduğumuz medianı döndürmemiz isteniyor.
Medyan (ya da ortanca) bir veri serisini(liste) küçükten büyüğe doğru sıraladığımızda, seriyi ortadan ikiye ayıran değere denir.
Örneğin; bize verilen liste arr = [5,4,3,1,2] gibi bir liste olsun. Medyan bulmak için sıralı bir listemiz olmak zorunda bu yüzden ilk önce listeyi sıralıyoruz. Sıralı listemiz arr = [1,2,3,4,5] olarak güncelleniyor. Bu listenin medianı 3 oluyor.
Tamam listenin uzunluğunun tek olması durumunda ortancasını listenin (n/2). değerli olarak bulabiliyoruz ama çift olması durumunda nasıl hareket etmeliyiz?
O zamanda arr = [1,2,3,4,5,6] elimizde şöyle bir liste olduğunu varsayalım. Listemizin hangi değerlerini alırsak ortancasını almış oluruz ona bakalım. Listenin (n/2) ve ( n/2) +1 değerlerini toplarsak ve ikiye bölersek medianımızı bulmjuş oluruz.
Çözüm: Önce listemizi sıralı bir şekle getiriyoruz. Yukarıda anlattığım listenin tek mi çift olduğuna bakıyoruz. Ve bulduğumuz sonuca göre medianı hesaplıyoruz.
Umarım anlaşılır ve açık olmuştur :) Time ve space complexityleri aşağıdaki gibi oluyor.
Time Complexity: O(log(n))
Space Complexity: O(1)
Farklı çözümleriniz olursa bizimle de paylaşın bir sonraji yazıya kadar kendinize iyi bakın :) 🪄
Çözümüne github üzerinden erişebilirsiniz 🎉
