平均轮数为零的子阵列数
你有一个整数数组。您必须找到子阵列的数量，该数量意味着（这些元素的总和除以这些元素的计数）舍入为零。我已经用O（n^2）时间解决了这个问题，但效率不够。有办法吗？
example:
[-1, 1, 5, 4]
subarrays which mean rounds to zero are:
[-1, 1] = 0 , [-1, 1, 5, -4] = 1/4 which rounds to zero
共有1个答案
表示由对(前缀总和，cnt)组成的新数组，其中第一个元素是前缀总和，第二个元素是元素的数量，例如，
int[] arr = [-1, 1, 5 ,4]:
int[] narr = [(0, 0), (-1, 1), (0, 2), (5, 3), (9, 4)]
该问题在narr中转换为计数对（i，j），其中i
narr[j][0] - j < narr[i][0] - i < narr[i][0] + i < narr[j][0] + j
于是问题进一步转化为如下问题:
对于某些间隔：[[1， 2]， [-1， 0]， ...]（最初是空的），给定一个区间 [x， y]，计算有多少个区间完全在 [x， y] 的范围内，然后我们加上这个区间，并重复此过程总共 N 次。（如何管理区间的数据结构成为关键问题）
如果我们只是暴力迭代每个间隔并进行验证，查询时间复杂度为O（N），插入时间复杂度为O（1），总O（N^2）
如果我们使用平方分解，查询时间复杂度为O（sqrt（N）），插入时间复杂度为O（1），总O（Nsqrt（N））
< del >如果我们使用treap(使用第一个或第二个作为优先级，使用另一个作为关键字)，我们可以实现的平均总时间复杂度为O(NlgN)
如果你不知道平方分解
或treap
的技术，我建议你先读几篇文章。
更新：
经过30分钟的仔细思考，我发现treap不能达到O(NlgN)平均时间复杂度。相反，我们可以使用2d段树来实现O(NlgNlgN):请改为阅读这篇文章:2d段树
-
我有一个正整数数组。例如： 一个“约简操作”找到平均值最高的数组前缀，并将其删除。这里，数组前缀是指左端为数组开始的连续子数组，如上面的或或。通过取较长的前缀来打破联系。 我将重复缩减操作，直到阵列为空： 现在，实际上执行这些数组修改是没有必要的；我只是在寻找这个过程将删除的前缀长度列表，例如上面的。 计算这些前缀长度的有效算法是什么？ 最简单的方法是重新计算算法的每次迭代中的所有总和和平均值——
-
问题内容： 我有一个大小为N *M的矩阵，我想找到每一行的平均值。值是从1到5，并且没有任何值的条目设置为0。但是，当我想使用以下方法查找均值时，它给了我错误的均值，因为它还计算了具有值的条目0。 如何获得仅非零值的均值？ 问题答案： 获取每一行的非零计数，并将其用于平均每一行的总和。因此，实现看起来像这样- 如果您使用的是较旧版本的NumPy，则可以使用count的float转换来替换，例如，
-
A=矩阵（c（1,2,3,0,2,2,0,2,3），nrow=3，ncol=3） B=矩阵（c（1,2,3,1,4,2,2,1），nrow=3，ncol=3） C=A B/（总和差为零） C=矩阵（c（1,2,3, 1, 3, 2, 2,2 ,2)，nrow=3，nco=3） 我需要对N个矩阵的列表执行此操作（mat_vect[[I]]）： 求和矩阵并得到平均值 这里是所有数字的除法，包括零。我不
-
我试图通过DP找到所有子数组的加权平均值，然后按列排序，找到长度相同的2。但我无法继续下去，我的方法似乎太模糊/太粗暴了。我将非常感谢任何帮助。提前谢了。
-
问题内容： 我有一个’DataFrame’，它偶尔会缺少值，看起来像这样： 我想在数据框中添加一个新的数据，以计算每个数据的平均值。 意思是，对于，我需要 ，但是对于，我只需要使用 有谁知道解决因缺失值导致的变化并计算平均值的最佳方法？ 问题答案： 您可以简单地： 因为默认情况下会忽略缺失值：请参阅docs。 要选择一个子集，您可以：
-
我想找到一种算法来计算阵列中不同子阵列的数量。 例如，在 A = [1，2，1，2] 的情况下，不同子数组的数量为 7： 在B=[1,1,1]的情况下，不同子阵列的数量为3: 子数组是数组的连续子序列或片段。不同意味着内容不同；例如: 来自A[0:1]的[1]和来自A[2:3]的[1]不是不同的。 类似地： B[0：1]，B[1：2]，B[2：3]并不明显。