如何处理整数矩阵求平均值的所有子矩形的O（1）中的元素？ [英] How to process a integer matrix to find the average for the elements of any sub-rectangle in O(1)?

问题描述

这是一个<一个href="http://www.glassdoor.com/Interview/Design-a-class-to-process-a-matrix-and-it-needs-to-be-able-to-return-the-average-for-the-elements-of-arbitrary-sub-rectang-QTN_142873.htm"相对=nofollow>面试问题：如何处理整数矩阵求平均值的所有子矩形的O（1）中的元素？正如评论所说，我们应该计算出preFIX款项。

This is an interview question: How to process a integer matrix to find the average for the elements of any sub-rectangle in O(1)? As the comments say, we should calculate the prefix sums.

嗯，这是令人尴尬的，但即使有问过类似的<一个href="http://stackoverflow.com/questions/5195446/how-to-$p$p-process-an-integer-array-to-find-an-average-of-any-subarray-in-o1">question我不明白。

Well, it is embarrassing but even having asked a similar question I did not get it.

推荐答案

请参阅@Sven Marnach'answer到了后@迈克尔链接。的preFIX总和算法他概述是基于以下想法：如果可以precomputed以下元件序列的总和：[0，0]，[0，1]，[0，2]，。 ..，[0，N-1]，可以计算序列之和[A，B]在恒定的时间为[0，B] - [0，A-1]。同样的想法可以应用于二维阵列。表示其左上角的子阵列的（a，b）和右下角在（C，D）为[（A，B），（C，D）。我们将同样对待这样一个子我们如何处理在1-D型序列。 precompute具有在其左上角（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，间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）]。画在纸上，你会看到的子阵列重叠的是如何以及为什么我们需要添加的最后一个子数组。

See @Sven Marnach'answer to the post @Michael linked to. The prefix sum algorithm he outlines is based on the following idea: if you have precomputed the sums of the following element sequences: [0, 0], [0, 1], [0, 2], ..., [0, n-1], you can compute the sum of the sequence [a, b] in constant time as [0, b] - [0, a-1]. The same idea can be applied to two-dimensional arrays. Denote the subarray with its upper left corner at (a, b) and its lower right corner at (c, d) as [(a, b), (c, d)]. We will treat such a subarray similarly to how we treated sequences in the 1-D case. Precompute the sums of all subarrays having their upper left corner at (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)]. There are n*m such subarrays, and the sum of each can be computed in constant time based on the sums of smaller subarrays. If we are now asked to produce the sum of the subarray [(a, b), (c, d)], we can find it as [(0, 0), (c, d)] - [(0, 0), (a-1, d)] - [(0, 0), (c, b-1)] + [(0, 0), (a-1, b-1)]. Draw it on paper, and you'll see how the subarrays overlap and why we need to add the last subarray.

这篇关于如何处理整数矩阵求平均值的所有子矩形的O（1）中的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！