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

Question

Это вопрос для собеседования : Как обработать целочисленную матрицу, чтобы найти среднее для элементов любого под прямоугольника в O (1)? Как говорится в комментариях, мы должны вычислить суммы префиксов.

Ну, это стыдно, но даже задав такой же вопрос 1006 * Я не получил его.

Answer 1

Хотя у вас есть несколько разумных ответов, это кажется вопросом, для которого картинка стоит нескольких тысяч слов.

Хорошо - мы хотим получить площадь прямоугольника 4. Однако наша предварительно вычисленная область говорит только об использовании области целого прямоугольника, начиная с начала координат в левом верхнем углу и продолжая к нижнему правому значению 4. Чтобы вычислить только площадь 4, мы должны вычесть области выше и влево (1, 2 и 3). Тем не менее, области 2 и 3 одинаковы: мы можем получить их области, начиная с верхнего левого угла и продолжая до нижнего правого. Это означает, что мы можем получить сумму их областей, , но площадь прямоугольника 1 включена в в обоих из них.

Итак, чтобы получить площадь прямоугольника 4, мы находим область в ее правом нижнем углу. Мы находим область в нижнем правом углу 2 и 3 и складываем их вместе. Затем мы вычитаем площадь в правом нижнем углу прямоугольника 1, поскольку она была включена в нашу общую сумму дважды. Это дает нам общую площадь прямоугольников 1, 2 и 3. Мы вычитаем ее из площади для нижнего правого угла прямоугольника 4, и это дает нам площадь прямоугольника 4 сама по себе.

Например, давайте предположим, что мне удалось получить все эти прямоугольники одинакового размера, поэтому мы будем называть область для каждого «1». Таким образом, площадь, указанная в правом нижнем углу каждого прямоугольника, будет:

1. 1
2. 2
3. 2
4. 4

Для простоты давайте определим каждый из них как pc_area(x) (то есть предварительно вычисленная область, которую мы получили бы в правом нижнем углу прямоугольника x).

Итак, мы берем: pc_area(4) - (pc_area(2) + pc_area(3) - pc_area(1)) Подставляя числа, мы получаем: 4 - (2 + 2 -1) или 4-3, что, очевидно, дает 1, ответ, который мы изначально определили как правильный.

Answer 2

См. @Sven Marnach'answer на пост @Michael, связанный с.Алгоритм суммирования префиксов, который он излагает, основан на следующей идее: если вы предварительно вычислили суммы следующих последовательностей элементов: [0, 0], [0, 1], [0, 2], ..., [0,n-1], вы можете вычислить сумму последовательности [a, b] за постоянное время как [0, b] - [0, a-1].Эта же идея может быть применена к двумерным массивам.Обозначим подмассив с его верхним левым углом в (a, b) и нижним правым углом в (c, d) как [(a, b), (c, d)].Мы будем относиться к такой подрешетке аналогично тому, как мы обрабатывали последовательности в одномерном случае.Предварительно вычислите суммы всех подмассивов, имеющих верхний левый угол в (0, 0): [(0, 0), (0, 0)], [(0, 0), (0, 1)], [(0,0), (0, 2)], ..., [(0, 0), (0, m-1)], [[(0, 0), (1, 0)], [(0, 0), (1, 1)], ..., [(0, 0), (1, m-1)], ..., [(0, 0), (n-1, m-1)],Таких подмассивов n * m, и сумма каждого из них может быть вычислена за постоянное время на основе сумм меньших подмассивов.Если нас теперь попросят получить сумму подмассива [(a, b), (c, d)], мы можем найти ее как [(0, 0), (c, d)] - [(0, 0), (a-1, d)] - [(0, 0), (c, b-1)] + [(0, 0), (a-1, b-1)].Нарисуйте его на бумаге, и вы увидите, как подмассивы перекрываются и почему нам нужно добавить последний подмассив.

Answer 3

Я думаю, что вас вводит в заблуждение предположение, что вы просто получаете матрицу / список чисел.

В этом случае требование невозможно.Самое быстрое, что вы могли бы сделать, - это эвристический алгоритм, основанный на алгоритме сортировки, и вы могли бы достичь O (Log (n)).

Это, однако, будет полезно только при наличии допуска на ошибки и распределениязначения не искажаются.

Но вы можете очень хорошо решить вашу проблему, если у вас есть контроль над структурой данных.Обычный способ сделать это называется prefix sums .

Читайте об этом в Википедии, они объясняют это лучше, чем я когда-либо мог.

Но позвольте мне привести очень простую тривиальную аналогию, которая может решить путаницу.

Вы не можетеискать элемент в списке в O (1).Log (n) - лучшее, что вы можете сделать, если он отсортирован или вы уже отсортировали его.

Однако, если у вас есть контроль над структурой данных, вы можете создать хеш-индекс, где вы можете непосредственно выбрать его и получить O(1).

Префиксные суммы - нечто похожее.Это структура данных, которая решает вашу проблему, а не алгоритм (ну, конечно, не алгоритм, а больше по другую сторону линии).