动态编程:在线性时间内可以找到偶数1和0的区间吗？

Question

在网上找到以下内容:

你有一个0和1的数组,你想输出所有的间隔(i,j),其中0的数量和1的数量是相等的.例

    pos = 0 1 2 3 4 5 6 7 8
          0 1 0 0 1 1 1 1 0

一个间隔是(0,1),因为0和1的数量相等.还有许多其他区间,在线性时间内找到所有区间.

我认为没有线性时间算法,因为可能有n ^ 2个这样的间隔.我对吗？我怎样才能证明有这样的n ^ 2？

Answer 1

这是我能想到的最快的方法,它与间隔的数量呈线性关系.

设L是原始的数字列表,A是空数组的哈希值,其中最初A [0] = [0]

sum = 0
for i in 0..n
  if L[i] == 0:
    sum--
    A[sum].push(i)
  elif L[i] == 1:
    sum++
    A[sum].push(i)

现在A本质上是序列之和的xy图(x是列表的索引,y是总和).每次有两个x值x1和x2到y值时,你有一个间隔(x1,x2),其中0和1的数量是相等的.

存在m(m-1)/ 2(从1到m-1的算术和)间隔,其中在A中的每个阵列M中总和为0,其中m = M.length

使用您的示例手动计算A,我们使用此图表

L           #   0  1  0  1  0  0  1  1  1  1  0
A keys      0  -1  0 -1  0 -1 -2 -1  0  1  2  1
L index    -1   0  1  2  3  4  5  6  7  8  9  10

(我添加了一个#来表示列表的开头,键为-1.同时删除了所有非0或1的数字,因为它们只是分散注意力)A将如下所示:

[-2]->[5]
[-1]->[0, 2, 4, 6]
[0]->[-1, 1, 3, 7]
[1]->[8, 10]
[2]->[9]

对于任何M = [a1,a2,a3,...],(ai + 1,aj)其中j> i将是具有与1s相同的0的数量的区间.例如,在[-1] - > [0,2,4,6]中,间隔为(1,2),(1,4),(1,6),(3,4),(3, 6),(5,6).

构建数组A是O(n),但是从A打印这些间隔必须在线性时间内完成间隔数.实际上,这可能是你的证据,即在n的线性时间内完成此操作是不可能的,因为它可能有比n更多的间隔,并且至少需要间隔迭代次数来打印它们.

当然,除非您认为构建A足以找到所有间隔(因为它从A显而易见的是间隔是什么),然后它与n:P成线性关系