Задача: 480. Sliding Window Median Сложность: 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⃣Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления. 😎 Решение: function medianSlidingWindow(&#036;nums, &#036;k) { &#036;medians = []; for (&#036;i = 0; &#036;i + &#036;k <= count(&#036;nums); &#036;i++) { &#036;window = array_slice(&#036;nums, &#036;i, &#036;k); sort(&#036;window); if (&#036;k % 2 == 1) { &#036;medians[] = &#036;window[&#036;k / 2]; } else { &#036;medians[] = (&#036;window[&#036;k / 2 - 1] + &#036;window[&#036;k / 2]) / 2.0; } } return &#036;medians; } Ставь 👍 и забирай 📚 Базу знаний