Сложность: Hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
👨💻 Алгоритм:
1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.
2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна.
3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.
😎 Решение:
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<double> MedianSlidingWindow(int[] nums, int k) {
List<double> medians = new List<double>();
for (int i = 0; i + k <= nums.Length; i++) {
int[] window = new int[k];
Array.Copy(nums, i, window, 0, k);
Array.Sort(window);
if (k % 2 == 1) {
medians.Add(window[k / 2]);
} else {
medians.Add((window[k / 2 - 1] + window[k / 2]) / 2.0);
}
}
return medians;
}
}
Ставь 👍 и забирай 📚 Базу знаний