长度为 n 的数组中长度为 3 的不同子序列的数量

Question

如何计算长度为n的数组中长度为3（或一般长度为k < n）的不同子序列的数量？

注意：如果两个子序列中元素的顺序不同，则认为两个子序列不同。

例：假设数组A = [1, 2, 1, 1]，那么答案应该是3，因为只有三个长度为3的不同子序列如下所示：

[1, 1, 1]
[1, 2, 1]
[2, 1, 1]

数组的大小n <= 10^5，数组中的每个元素A_i <= n。

我的做法：

我想到了蛮力方法，即将长度为 3 的元组插入到地图中。但这既不 space/time 有效。

编辑：这是一道面试题，它说for k = 3 预计时间和space 复杂度是 O(n).

Answer 1

与面试问题的情况一样，有一个动态规划解决方案。令 T(m, k) 为第一个 m 元素的不同长度 - k 子序列的数量。然后假设对输入 A 进行基于一的索引，我们有一个二维递归

T(m, 0) = 1
T(m, k) = T(m-1, k) + T(m-1, k-1) -
          ^^^^^^^^^   ^^^^^^^^^^^
     A_m not chosen   A_m chosen

            { T(i-1, k-1), if i < m is the maximum index where A_i = A_m
            { 0,           if no such index exists

减去的项确保我们不计算重复项；有关更多说明，请参阅。

运行时间（使用散列映射来维护到目前为止所见每个符号最右边的出现）是 O(k n)，对于 k = 3 是 O(n)。

Answer 2

这里的看法略有不同。我们可以将一个元素 m 在子序列中第 k 的方式的数量视为任何元素（包括 m ）先前出现的所有方式的总和第 (k-1)。然而，当我们向右移动时，唯一需要更新的是 m；其他总和保持不变。

例如，

// We want to avoid counting [1,1,1], [1,2,1], etc. twice
[1, 2, 1, 1, 1]

（为了方便竖排显示数组）

            <-  k  ->
[1,  ->  1: [1, 0, 0]
 2,  ->  2: [1, 1, 0]
 1,  ->  1: [1, 2, 1]
 1,  ->  1: [1, 2, 3]
 1]  ->  1: [1, 2, 3]

现在如果我们添加另一个元素，比如 3，

...
 3]  ->  3: [1, 2, 3]

 // 1 means there is one way
 // the element, 3, can be first

 // 2 means there are 2 ways
 // 3 can be second: sum distinct
 // column k[0] = 1 + 1 = 2

 // 3 means there are 3 ways
 // 3 can be third: sum distinct
 // column k[1] = 2 + 1 = 3

不同 k[2] 列的总和：

0 + 3 + 3 = 6 subsequences

[1,2,1], [2,1,1], [1,1,1]
[1,1,3], [2,1,3], [3,2,1]

每列的 sum-distinct 可以在每次迭代 O(1) 中更新。当前元素的 k 总和（我们为每个元素更新一个列表），取 O(k)，在我们的例子中是 O(1).

JavaScript代码：

function f(A, k){
  A.unshift(null);
  
  let sumDistinct = new Array(k + 1).fill(0);
  let hash = {};

  sumDistinct[0] = 1;

  for (let i=1; i<A.length; i++){
    let newElement;
    
    if (!hash[A[i]]){
      hash[A[i]] = new Array(k + 1).fill(0);
      newElement = true;
    }
    
    let prev = hash[A[i]].slice();

    // The number of ways an element, m, can be k'th
    // in the subsequence is the sum of all the ways
    // the previous occurence of any element
    // (including m) can be (k-1)'th
    for (let j=1; j<=k && j<=i; j++)
      hash[A[i]][j] = sumDistinct[j - 1];

    for (let j=2; j<=k && j<=i; j++)
      sumDistinct[j] = sumDistinct[j] - prev[j] + hash[A[i]][j];

    if (newElement)
      sumDistinct[1] += 1;

    console.log(JSON.stringify([A[i], hash[A[i]], sumDistinct]))
  }

  return sumDistinct[k];
}

var arr = [1, 2, 1, 1, 1, 3, 2, 1];

console.log(f(arr, 3));

长度为 n 的数组中长度为 3 的不同子序列的数量

No. of distinct subsequences of length 3 in an array of length n

arrays

algorithm

math

counting

dynamic-programming