Sliding Window Median

Sizga nums butun sonlar massivi va k oynaning o'lchami (sliding window size) berilgan. Oyna massivning boshidan boshlab oxirigacha har safar bitta qadam (bir element) o'ngga siljiydi.

Siz har bir oynadagi elementlarning medianasini topishingiz va natijada barcha medianalardan iborat massivni qaytarishingiz kerak. Agar elementlar soni juft bo'lsa, mediana — o'rtadagi ikkita elementning o'rtachasidir.

func solve(nums []int, k int) []float64 {
    // ...
}

Misollar

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.0,-1.0,-1.0,3.0,5.0,6.0]
Tushuntirish:
Oynalar va ularning medianalari:
[1 3 -1] -> [-1, 1, 3] -> 1
[3 -1 -3] -> [-3, -1, 3] -> -1
[-1 -3 5] -> [-3, -1, 5] -> -1
[-3 5 3] -> [-3, 3, 5] -> 3
[5 3 6] -> [3, 5, 6] -> 5
[3 6 7] -> [3, 6, 7] -> 6

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.0, 3.0, 3.0, 3.0, 2.0, 3.0, 2.0]

Input: nums = [5], k = 1
Output: [5]

Input: nums = [1, 2], k = 2
Output: [1.5]

Maslahatlar

1. Oynani har safar boshidan saralashning hojati yo'q — o'lchami k bo'lgan saralangan massiv (yoki tuzilma) ni saqlab, oyna siljiganda faqat bitta eski elementni chiqarib, bitta yangisini kiritishni o'ylab ko'ring.
2. Boshlang'ich k ta elementni saralab oling. Har bir siljishda: chiqib ketayotgan elementni binar qidiruv (sort.SearchInts) yordamida saralangan massivda topib o'chiring, keyin kirayotgan yangi elementni ham binar qidiruv bilan to'g'ri joyiga qo'shib qo'ying (slice ichiga joylash). Har bir oyna uchun saralangan massiv o'rtasidagi (yoki ikkita o'rta elementning o'rtachasi) qiymatni medianasi sifatida qaytaring.