1

假设 S 是一个只包含 0 和 1 的字符串。我想计算 S 的非空子字符串的数量，其中 0 的数量小于 1 的数量。

使用下面给出的蛮力方法，我们可以有一个算法在 O(n^2) 中解决这个问题：

moreOnes(s):
count = 0
n = s.len()

for i = 1 to n
    one = 0
    zero = 0
    for j = i to n
        if s[i] == '1'
            one++
        else
            zero++
        
        if one > zero
            count++

return count

但是我们能不能有一个更好的时间复杂度为 O(n*logn) 或 O(n) 的算法，并且空间复杂度是从 O(1) 到 O(n) 的任何值？

4

1 回答 1

2

考虑一个数组 A[i]，它包含范围 1..i 中的 1 的数量减去范围 1..i 中的零的数量。

使用这个数组，现在只需 O(1) 时间即可通过计算 A[j]-A[i-1] 来计算 i..j 中子字符串中 1 的数量减去 0 的数量。

对于给定的端点 j，您希望找到所有起点 i<=j 使得A[j]-A[i-1]>0. 等效地，您想知道有多少 A[i-1] 的值小于 A[j]。

这可以通过Fenwick 树解决：

  1. 循环 j
  2. A[j]在 Fenwick 树中的位置添加 1
  3. 从 Fenwick 树中查找累积值，范围为A[j]-1- 这是以 j 结尾并满足多于零的所需属性的子字符串的数量。

这将占用 Fenwick 树的 O(n) 空间和 O(nlogn) 时间，因为每次查找都是 O(logn)。

（请注意，A[j] 可能会变为负数，而 Fenwick 树通常使用正数数据。您可以通过将 n 的恒定偏移量添加到 A[j] 来解决此问题，因此所有条目都是正数。）

于 2021-07-10T09:32:44.967 回答