Замените все элементы данного массива средним значением предыдущих K и следующих K элементов.

Дан массив arr[] , содержащий N положительных целых чисел и целое число K. Задача состоит в том, чтобы заменить каждый элемент массива средним значением K предыдущих и следующих K элементов. Кроме того, если элементы K отсутствуют, настройте максимальное количество элементов, доступных до и после.

Примеры:

Input: arr[] = {9, 7, 3, 9, 1, 8, 11}, K=2
Output: 5 7 6 4 7 7 4
Explanation: For i = 0, average = (7 + 3)/2 = 5
For i = 1, average = (9 + 3 + 9)/3 = 7
For i = 2, average = (9 + 7 + 9 + 1)/4 = 6
For i = 3, average = (7 + 3 + 1 + 8)/4 = 4
For i = 4, average = (3 + 9 + 8 + 11)/4 = 7
For i = 5, average = (9 + 1 + 11)/3 = 7
For i = 6, average = (1 + 8)/2 = 4

Input: arr[] = {13, 26, 35, 41, 23, 18, 38}, K=3
Output: 34 28 24 25 31 34 27 

Наивный подход: самый простой подход — использовать вложенные циклы. Внешний цикл будет проходить по массиву слева направо, т. е. от i = 0 до i < N , а внутренний цикл будет проходить по подмассиву от индекса i – K до индекса i + K , кроме i , и вычислять среднее из них.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: О(1)

Эффективный подход: этот подход использует метод скользящего окна. Следуйте шагам, указанным ниже, чтобы реализовать эту концепцию:

• Учтите, что каждый элемент имеет K следующих и предыдущих элементов, и возьмем окно размером 2*K + 1, чтобы покрыть весь этот диапазон.
• Теперь сначала найдите сумму первых (K+1) элементов.
• При обходе массива:
  • Рассчитайте среднее значение, разделив сумму на (размер окна-1).
  • Добавьте следующий элемент после крайнего правого конца текущего окна.
  • Удалить крайний левый элемент текущего окна. Это сдвинет окно на одну позицию вправо
• Распечатайте полученный массив.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)