Постановка задачи

Найдите среднее значение каждого подмассива из "K" смежных элементов в нем.

Привет, амигос, в этой статье мы рассмотрим один из наиболее часто задаваемых вопросов на собеседованиях по программированию и рассмотрим его решение с помощью двух основных подходов.

Во-первых, давайте разберемся с постановкой задачи

Рассмотрим массив как Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], а K равен K=5

здесь нам нужно вычислить среднее значение подмассива, граничащего со значением K.

Таким образом, пример подмассива и его среднего значения будет

Для первых 5 чисел (подмассив из индекса 0–4) среднее значение равно: (1+3+2+6–1)/5 = 2,2.

Для второго числа 5 (подмассив из индекса 1–5) среднее значение равно: (3+2+6–1+4)/5 = 2,8.

так далее, тогда окончательный результат Output: [2.2, 2.8, 2.4, 3.6, 2.8]

Давайте рассмотрим его первый подход

здесь мы рассмотрим два основных подхода

Первый подход прост и прямолинеен, он суммирует все 5-элементные подмассивы данного массива и делит сумму на «5», чтобы найти среднее значение.

Если вы видите приведенный выше код, вы можете легко понять, что мы перебираем каждый элемент массива и вычисляем сумму первых 5 элементов. Сумма непрерывного подмассива определяется значением K, которое задается как K=5

Приведенное выше решение простое, и это обычное решение, которое приходит всем на ум.

Итак, давайте попробуем подумать🤔 есть ли какой-либо другой доступный подход, который предоставит решение, и решение будет более оптимизированным?

Вышеприведенное решение содержит повторяющиеся шаги, и если мы вычислим его временную сложность, оно будет O(N∗K) где «N» — количество элементов во входном массиве.

Давайте посмотрим на его второй подход

Итак, есть ли какой-либо алгоритм или способ оптимизации решения? Если вы спросите меня, то ДА. Здесь мы будем использовать подход Sliding Window.

Мы не будем углубляться в алгоритм скользящего окна. но мы можем решить вышеупомянутую проблему, используя эту технику, которая даст вам основную идею.

Здесь мы сдвинем окно на один элемент, когда перейдем к следующему подмассиву. Чтобы повторно использовать sum из предыдущего подмассива, мы вычтем элемент, выходящий из окна, и добавим элемент, который сейчас включается в скользящее окно. Это избавит нас от обхода всего подмассива в поисках sum и, как следствие, сложность алгоритма уменьшится до O(N).

Чтобы лучше понять, вот ссылка на видео