让我们给问题命名一些名称:
m = 数组序列的长度(例如您的示例中为14)
n = 数组序列中唯一元素的总数(例如示例中为3)
k = 每个搜索区域的长度(例如示例中为5)
g = 您要查找的组数(例如示例中为2)
一种选择是在每个大小为k的搜索区域中总结您的数据。在您的示例中,如下所示:
{B A x x C}
{A x x C x}
...
我们为每个部分创建大小为n
的向量,第一个元素表示第一种元素的出现情况,比如A
B A x x C --> [1,1,1] (one appearance of each)
A x x C x --> [1,0,1]
我们可以对我们正在搜索的群组执行相同的操作:
等等。
{A A C} --> [2,0,1]
{A B C} --> [1,1,1]
现在问题变得很明显。假设我们考虑搜索区域的摘要 [3,2,5] 和我们要搜索的一组摘要 [0,1,2],我们可以通过认识到第二个元素有两种选择,以及对于第三个元素有 (5x4)/(1x2) 种选择来计算组合数,因此总共有20种选择。
因此,对于区域摘要 S[s
1, s
2,..,s
n] 和一个单独的感兴趣的组 G[g
1, g
2,...g
n],我们可以计算从 S 中提取 G 的总方法数(C++风格代码,除非 "!" 表示阶乘):
int total_options = 1;
for (int i = 0; i < n; ++i)
{
if(g[i] == 0)
continue;
if(s[i] < g[i])
return 0;
for (int d = 1, f = s[i]; f > max(g[i], s[i] - g[i]); --f, ++d)
total_options = total_options / d * f;
}
return total_options;
您需要为每个部分和每个搜索组执行此操作。
时间复杂度:O(g*m*(k+n))(由于最坏情况下的阶乘计算,我们必须包括k)
空间复杂度:O(m+g*n)(我们可以在进行计算时计算每个部分,因此无需同时存储多个部分)
然后,我们可以通过意识到每个连续的“部分”只是考虑到离开的“尾”元素和进入的“头”元素而不同来改进它,因此我们应该计算这两个如何将“选项计数”更改为我们迭代到下一个部分。我们将通过维护先前的“选项计数”计算和NF(失败数)来执行此操作,即区域中太低以至于无法满足搜索组的元素数量。诀窍是维护一个正的“选项计数”,仅当NF为0时才将其添加到总数中。这将使您在迭代大小为m的主数组时为每个G提供常量时间结果。
时间复杂度:O(g*m+g*n)
空间复杂度:O(g*n+m)
当主数组中的每个元素都是唯一的,并且这些元素中的每个元素都至少出现在某些搜索中时,此算法具有最坏情况性能(否则,我们可以将不出现在任何搜索中的任何元素视为相同,例如您的示例中的“x”)。因此,最坏情况下的复杂性可以简化为:
时间复杂度:O(g*m)
空间复杂度:O(g*m)
我看不出如何可能获得更好的时间复杂度,但如果有聪明人能想出具有较低空间复杂度的方法,我会很感兴趣。
如果您不知道仅通过考虑头和尾进行常量时间迭代是什么意思,请告诉我,我将用示例说明。