找到具有最佳复杂性的数组中唯一连续增加的子序列的数量

Question

假设给定一个数组 [1, 2, 3, ..., n]。现在随机洗牌。最好的方法是什么（就时间和 space 复杂性而言，在打乱后的数组中找到唯一连续增加的子序列的数量？

例如，a=[1,2,3,6,5,4,7,8,9] 有3个这样的子序列： [1,2,3,4], [6,7,8,9], [5]。（[5] 简单地满足定义）

提前致谢。

编辑：我在想的一种方法是，每当我们遇到一个新元素时，检查它是否是前一个元素的+1，如果不是，则将其放入一个新数组中。但是当有很多这样的数组时，检查下一个元素是否是任何现有数组的最后一个元素的 +1 需要更长的时间。所以 space 复杂度是 n，但是在最坏情况下 a=[n,n-1,n-2,...,1] 所花费的时间是 1 + 2 + 3 +...+ n- 1=O(n^2)。但可能有更好的方法。

编辑 2：抱歉，我刚刚意识到能够输出这些子序列的显式形式也很重要（如给出的示例所示）。所以有两种最好的复杂度情况，一种用于计算数量，另一种用于输出显式。

Answer 1

我想出了这个（在 Java）：

public int countSubSequences(int[] array){
    int numberOfSubSequences = 0;
    for (int i = 0; i < array.length-1; i++) {
        if(array[i]>array[i+1]){
            numberOfSubSequences++;
        }
    }
    numberOfSubSequences++;
    return numberOfSubSequences;
}

我只是遍历数组并检查数组中的下一个元素是否小于我的当前元素。如果是这种情况，则当前元素是子序列的末尾，我们可以增加我们的计数。在返回之前我们也需要递增，因为数组的末尾也是最后一个子序列的末尾。

时间复杂度是线性的，所以 O=(n) 和 space 复杂度应该是常数 O=(1) 因为我们不需要记住使用此方法的子序列来计算它们。

Answer 2

您可以通过计算连胜开始来计算连胜。值 x 是连胜的开始，前提是您之前没有见过 x - 1。在您的示例中，这是 1、6 和 5。需要 O(n) 时间和 space.

a = [1,2,3,6,5,4,7,8,9]

streaks = 0
seen = set()
for x in a:
    if x - 1 not in seen:
        streaks += 1
    seen.add(x)

print(streaks)

输出，Try it online!：

可以是 O(1) space 如果你允许修改 a （例如，记住 x 就像通过否定 a[x-1] 看到的那样）。

a = [1,2,3,6,5,4,7,8,9]

streaks = 0
for x in map(abs, a):
    if a[x-2] > 0:
        streaks += 1
    a[x-1] *= -1

print(streaks)

输出，Try it online!：

一个版本收集了条纹，O(n) 时间和space:

a = [1,2,3,6,5,4,7,8,9]

streaks = {}
for x in a:
    streak = streaks.pop(x - 1, [])
    streak.append(x)
    streaks[x] = streak

print(*streaks.values())

输出，Try it online!：

[5] [1, 2, 3, 4] [6, 7, 8, 9]

找到具有最佳复杂性的数组中唯一连续增加的子序列的数量

Find the number of unique consecutively increasing subsequences in an array with best complexity

sorting

counting

time-complexity

space-complexity