arrays - 如何改进Increasing Subsequences算法以合并未排序的数组？

Question

我一直致力于解决递增子序列问题。我想出的算法目前只解决排序数组。我正在用 python 3.5 编写代码。这个问题托管在 Leetcode 上。

在递增子序列问题中，给我一个整数数组，任务是找到给定数组的所有不同可能的递增子序列，递增子序列的长度至少应为 2。

例子:

输入- [4,6,7,7]

输出 - [[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7,7], [7,7],[4,7,7]]

这是我解决这个问题的工作代码:

array = [4,6,7,7]

def incrSubseq(array): #Only works for sorted arrays.
    res = [[]]
    ans = []
    for num in array:
        res += [item + [num] for item in res if (item+[num] not in res)]
    for values in res:
        if len(values)>1:
            ans = ans + [values]
    print(ans)
incrSubseq(array)

这段代码是如何工作的？

1. 首先初始化一个结果变量res (列表列表)它由一个空列表初始化。
2. 然后我遍历给定的整数数组 array这是按排序顺序，将每个元素添加到列表中，从而找到可以形成的所有子集。 if列表理解中的语句过滤掉重复的项目，因此只保留列表的一个副本。
3. 然后过滤掉所有长度大于1的数组。

这样，问题就解决了。

现在，我在这里缺少的是解决未排序数组的方法。据我了解，当我尝试向 res 添加元素时，我需要进行检查。它应该大于或等于它之前的项目。

res += [item + [num] for item in res if (item+[num] not in res) and (item <= num)]给出空列表。

有什么改进代码的建议吗？

Answer 1

你的想法完全正确!只需检查 item 中的最后一个元素是否比以前小(可能允许相等，取决于如何定义增加)。

所以你添加支票 item[-1] <= num (用 -1 可以得到 Python 中数组的最后一个元素)。

现在还有一个问题。 item可能是空的，你会得到一个错误。所以你只想要 <=检查 item 中是否至少有一个元素.下面是一个使用 bool 运算短路的奇特解决方案，其中 (len(item) == 0 or item[-1] <= num)当没有元素(那么第二次检查不执行)，或者 item 中至少有一个元素时为真然后检查它是否小于或等于。

array = [4,6,3,7]

def incrSubseq(array): # Works for sorted arrays too :)
    res = [[]]

    for num in array:
        res += [item + [num] for item in res if (item + [num] not in res 
                                                 and (len(item) == 0 or item[-1] <= num))]

    return [values for values in res if len(values) > 1]

print(incrSubseq(array))

---

Short circuiting 表示仅在可以确定其最终值之前评估 bool 表达式。例如False and 1/0不会引发异常，因为 and是False如果任何它的两个参数是False .因此，当评估从左到右进行时，它不会计算 1/0。 .

更详细一点，上述算法的内部部分可以写成:

for num in array:
    for item in res:
        if item + [num] not in res:
            if len(item) == 0:
                # item is empty.
                res += [num]
            else:
                # item is not empty so we check its last element.
                if item[-1] <= num:
                    res += item + [num]
                else:
                    # We got something increasing here. Do not add.
                    pass

---

该算法的复杂度可以计算如下。假设最坏情况下输入 [1, 2, ..., n] .然后在每一步中，结果子序列的数量加倍，导致 O(2^n)子序列和 O(n * 2^n) 的输出大小.每个算法都至少需要那么长的时间(如果你真的对输出每个序列感兴趣——如果你想动态生成所有东西，也就是函数式语言的迭代器和惰性求值风格，这无关紧要)。

虽然这个算法需要更长的时间。我们必须为输出中的每个子序列做的主要工作是检查它是否会重复执行天真的 item + [num] not in res。 .两个长度为 m 的列表的比较需要 O(m)最坏的情况下。考虑到最后一个 num占总运行时间的一半以上，我们在这里只是将其用作一个很好的近似值。这意味着检查最后一个 2^(n-1)创建的子序列需要 O(2^(n-1) * 2^(n-1) * n) = O(n * 4^n)因为你用每一个旧序列检查每一个新序列。用prefix tree作为结果数据结构，这可以减少到只有 O(2^n)因为检查新子序列是否有效只需要 O(1) .遍历树以实际写下所有解决方案需要再次 O(2^n * n) .

旁注:如果您喜欢 python 中的函数式编程，请查看 syntax_sugar_python ,