Вычислите сумму элементов в матрице эффективно
В интервью меня спросили, дали ли мне n*m матрицу, как вычислить сумму значений в данной субматрице (определенный верхними левыми, нижними правыми координатами).
Мне сказали, что я мог предварительно обработать матрицу.
Мне сказали, что матрица могла быть значительной, и так мог субматрица, таким образом, алгоритм должен был быть эффективным. Я споткнулся немного и не был сказан лучший ответ.
У кого-либо есть хороший ответ?
3 ответа
Вот для чего нужны таблицы суммированных областей. http://en.wikipedia.org/wiki/Summed_area_table
Ваш шаг "предварительной обработки" заключается в построении новой матрицы того же размера, где каждая запись является суммой подматрицы, находящейся слева вверху от этой записи. Любая произвольная сумма подматрицы может быть вычислена путем поиска и смешивания только 4 записей в SAT.
EDIT: Вот пример.
Для исходной матрицы
0 1 4
2 3 2
1 2 7
SAT есть
0 1 5
2 6 12
3 9 22
SAT получается с помощью S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1),
где S - матрица SAT, a - исходная матрица.
Если вам нужна сумма правой нижней подматрицы 2x2, то ответ будет 22 + 0 - 3 - 5 = 14. Что, очевидно, то же самое, что 3 + 2 + 2 + 7. Независимо от размера матрицы, сумма подматрицы может быть найдена за 4 поиска и 3 арифметических операции. Построение SAT является O(n), аналогично требуя только 4 поиска и 3 математических операции на клетку.
Создайте новую матрицу, где запись (i, j) представляет собой сумму элементов исходной матрицы, которые имеют меньшее или равное i и j . Затем, чтобы найти сумму элементов в подматрице, вы можете просто использовать постоянное количество основных операций, используя углы подматрицы вашей матрицы суммы.
В частности, найдите углы top_left, bottom_left, top_right и bottom_right вашей матрицы суммы, где первые три находятся сразу за пределами подматрицы, а bottom_right только внутри. Тогда ваша сумма будет
bottom_right + top_left - bottom_left - bottom_right
Это должно сработать. Вам всегда нужно просматривать каждый элемент в подматрице, чтобы выполнить сложение, и это самый простой способ.
* обратите внимание, что следующий код может не компилироваться, но он находится прямо в псевдокоде
struct Coords{
int x,y;
}
int SumSubMatrix(Coords topleft, Coords bottomright, int** matrix){
int localsum = 0;
for( int i = topleft.x; i <= bottomright.x; i++ ){
for(int j = topleft.y; j <= bottomright.y; j++){
localsum += matrix[i][j];
}
}
return localsum;
}
Изменить: Альтернативный метод предварительной обработки - создать другую матрицу из оригинала, содержащую суммы строк или столбцов. Вот пример: Оригинал:
0 1 4 2 3 2 1 2 7
Матрица строк:
0 1 5 2 5 7 1 3 10
Матрица столбцов:
0 1 4 2 4 6 3 6 13
Теперь просто возьмите значения x конечной точки и вычтите значения начальной точки, например (для строк):
for( int i = topleft.y; i >= bottomright.y; i++ ){
localsum += matrix2[bottomright.x][i] - matrix2[topleft.x][i];
}
Теперь это либо O (n), либо O (m)