Как предварительно обработать целочисленный массив, чтобы найти среднее значение любого подмассива в O (1)?

Question

Эта проблема перефразирует вопрос для интервью . Поскольку эта первоначальная проблема кажется мне слишком сложной, я пытаюсь решить более простую: как обработать целочисленный массив, чтобы найти среднее значение любого подмассива за постоянное время. Очевидно, что мы можем обработать все вложенные массивы в O(n^2). Есть ли лучшие решения?

Answer 1

Для случая 1d: вычислите кумулятивные суммы массива, т.е. данного массива a, определите b с помощью

b[0] = a[0];
for (int i = 1; i < n; ++i)
    b[i] = b[i - 1] + a[i];

Чтобы вычислить любое среднее значение для подмассива, вычислите разностьнакопленная сумма, соответствующая конечному индексу и соответствующему начальному индексу, и деленная на количество записей в подмассиве.Например, для диапазона от i+1 до j, выполните

average = (b[j] - b[i]) / (double)(j - i);

То же самое работает в двух измерениях, вычисляя кумулятивные суммы по двум осям.

Answer 2

Я бы использовал нулевой индекс каждого подмассива (или новый одномерный массив длины первого измерения зубчатого массива) для хранения среднего и вычисления этого среднего, пока элементы добавляются в массив.Вы можете вычислить среднее из N + 1 элементов, учитывая среднее из N элементов и +1 элемент, в постоянное время, взвешивая существующее среднее значение для N элементов, составляющих его.Это означает, что заполнение массива все еще является линейным, и после заполнения у вас есть среднее значение в индексированной памяти (фактически извлечение в постоянном времени).

РЕДАКТИРОВАТЬ: Метод усреднения в постоянное время непросто "довольно близко";математически доказано, что среднее из N элементов, умноженных на N, плюс еще один элемент, разделенный на N + 1, точно равно среднему из N + 1 элементов в общем случае.Среднее значение множества S, умноженное на его мощность N, равно сумме множества S, поэтому для любого непустого множества S мощности N:

avg(S) = sum(S) / count(S)
S' = S + {X}
avg(S') = sum(S') / count(S')
        = (sum(S) + X) / count(S')
        = ((avg(S) * N) + X) / count(S') //QED

ВНОВЬ РЕДАКТИРОВАТЬ: Упсмое решение для многомерного зубчатого массива.ОК, не важно.В этом случае я бы создал массив, содержащий накопленную сумму для каждого элемента всех элементов от первого до текущего.Затем, чтобы вычислить среднее значение любого смежного подмассива, вычтите совокупную сумму элемента перед начальным индексом (или ноль, если он начинается с первого индекса) из совокупной суммы конечного индекса и разделите на разницу междуначальный и конечный индексы плюс 1.

... что является ответом Свена.