algorithm - 计算二进制数组中零个数大于一的子数组的数量

Question

给定一个二进制数组。找到其中零个数大于一的子数组的数量？

我已经设法制定出一个天真的 O(N2) 解决方案，是否有可能变得更好？

标签： algorithmsub-array

Answer 1

您调用 F[i] 是从 a[1] 到 a[i] 的第 1 位的数量；G[i] 是从 a[1] 到 a[i] 的位 0 的数量。所以我们必须找到对 i,j (0<=i<j<=n) 的数量：F[j]-F[i]< G[j]-G[i]。

它可能需要 O(N^2)，但如果我们转换该表达式：

F[j] - F[i]< G[j] - G[i]

<=> F[j] - G[j] < F[i] - G[i] (*)

如果我们调用C[i] = F[i]- G[i]，那么：

(*) <=> C[j] < C[i]。

问题将变为：找到i < j和C[i] > C[j]的对 (i, j) 的数量。我们可以在大约O(NlogN)中轻松地用二叉搜索树解决