0

给定一个长度为 n 的数组，对于每个索引 i 都有一个整数 xi (xi<=i)。我需要计算所有包含这两个索引的连续子序列，例如也不应该重复。我已经计算了子序列 [1,4] 说（i = 4 && x4 = 0），那么如果下一个（i = 5 && x5 = 1）我不应该两次包含相同的连续序列。我需要找到所有这些子序列的计数。我尝试了蛮力方法，但不足以打败时间。

我可以有更好的方法吗？可能是 O(NLOGN) 或更少？

4

1 回答 1

1

解决方案非常简单明了。

假设我们正在为索引 i 执行此操作。

我们通过将子序列扩展到限制（索引）x[i]和i之外来生成子序列，因为子序列总是将数组的元素从x[i] 带到 i，如果我们只扩展，我们的子序列将始终具有索引x [我]和我。

但是，当然，我们还将涵盖从x[i]到i的明显子序列，这是第一个子序列。

编辑：为避免重复，我们必须检查给定的左右边界组合是否已尝试过。

为此，我们将制作一个邻接列表，其中包含

N 个链表。

并且所有链表最初都是空的。

现在，具有相应左右边界的给定子序列之前没有被尝试过当且仅当

linked list arr[left] does not contain element right.

如果链表 arr[left] 包含元素 right 则表示该子序列之前已打印过。

首先，我们将子序列的左边界固定为 x[i]，然后使用新的左边界，我们尝试所有可能的新右边界，它们是：

i,i+1,i+2 ....... N-1 , N is equal to length of array a.

Corresponding subsequenes being
if(a[j] linked list does not contain i)
 {
   print the subsequence a[j],a[j+1],......a[i]
   add i to arr[j]
 }
if(a[j] linked list does not contain i+1)
 {
   print the subsequence a[j],a[j+1],.........a[i+1]
   add i+1 to a[j]
 }

and similar if condition before all subsequences given below.      

a[j],a[j+1],...............a[i+2]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i] for the above subsequences.

然后我们将左边界固定为 x[i]-1，然后使用新的左边界我们尝试所有可能的新右边界，它们是：

i,i+1,i+2 ....... N-1

相应的子序列是

similar if condition as given above before all subsequences given below.      
and they will be printed if and only if the condition is true.

a[j],a[j+1],.........a[i]
a[j],a[j+1],...............a[i+1]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i]-1 for the above subsequences.

我们这样做直到 j 变为 0，这将是最后一次迭代。

现在谈到这个算法的效率，因为在每一步我都在生成一个新的子序列，并且没有一个步骤浪费在生成一个不包含两个索引的子序列上，所以我认为它非常有效。

于 2015-08-10T13:45:21.303 回答