如何pre-过程中的整数数组找到O（1）平均任何子阵的？ [英] How to pre-process an integer array to find an average of any subarray in O(1)?

问题描述

这个问题rephrases的<一个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（n ^ 2）。有没有更好的办法呢？

This problem rephrases an interview question. Since this original problem seems too hard to me I am trying to solve a simpler one: how to process an integer array to find an average of any sub-array in constant time. Obviously, we can process all sub-arrays in O(n^2). Are there better solutions?

推荐答案

对于1D情况：计算数组的累积和，我。即定的数组 A ，定义 B 按

For the 1d case: compute the cumulative sums of the array, i. e. given array a, define b by

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

要计算任何平均一个子阵列，计算cumultaive总和通过在子阵列中的条目数corrseponding到结束索引和对应于所述起始索引的一个，分频的差。例如，对于范围从 I + 1 到Ĵ，执行

To compute any average of a subarray, compute the difference of the cumultaive sum corrseponding to the end index and the one corresponding to the start index, and divide by the number of entries in the subarray. For example for the range from i+1 to j, do

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

同样的事情，通过计算累加和沿两轴工作在两个方面。

The same thing works in two dimensions by computing cumulative sums along the two axes.

这篇关于如何pre-过程中的整数数组找到O（1）平均任何子阵的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！