algorithm - 交替 bool 范围的二维正交加法投影

Question

我有几个可变长度的数组，其中填充了表示好数据 block 和坏数据 block 的元组。

input = [
    [(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
    [(True, 0, 200), (False, 200, 400), (True, 400, 1000)],
    [(False, 0, 100), (True, 100, 1000])]]

我想要做的是创建一个新的元组列表，这些元组表示在我的所有数组中都很好的数据 block 。上面的结果如下。

output = [(False, 0, 100), (True, 100, 200), (False, 200, 500), 
         (True, 500, 1000)]

每个原始数组中的元组保证交替为 True 和 False。每个数组也将具有相同的开始和结束(在上述情况下为 0 和 1000)。

test = fn(input)
assert test == output

我的目标是在 O(n) 时间内完成这项工作，但我一直无法弄清楚。

Answer 1

基本上，您想要合并数组。您可以成对进行:首先，将第一个数组与第二个数组合并，然后将结果与第三个数组合并，依此类推。

如何合并两个数组？运行一个有两个索引的循环，当在第一个数组上时，第二个在第二个数组上。在每次循环迭代中，您递增其中一个索引，该索引代表具有较低数据位置的元组。然后逐个元组合并数组。

例如，让我们先考虑两个数组。

[(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
[(True, 0, 200), (False, 200, 400), (True, 400, 1000)],

我们开始时 i 指向 (True, 0, 400) 和 j 指向 (True, 0, 200 )。 None 为假，所以我们的输出以 (True, 0, 200) 开始(这两个元组的公共(public)部分)。然后我们递增 j(因为它的元组以 200 结尾)。

在下一次迭代中，i 和 j 指向元组 (True, 0, 400) 和 (False, 200, 400)，分别。我们合并它们，得到 (False, 200, 400)，我们将其添加到我们的输出中。现在两个元组都以相同的数据位置结尾，所以我们都递增。

接下来，我们得到元组 (False, 400, 500) 和 (True, 400, 1000)。我们合并它们以获得 (False, 400, 500)。因为我们输出中的最后一个元组是 False，所以我们没有再添加一个 False 元组，而是简单地将输出中的最后一个元组扩展到 500。我们递增 i。

在最后一次迭代中，我们有 (True, 500, 1000) 和 (True, 400, 1000) 我们合并得到 (True, 500, 1000)。

因此，我们的输出是 [(True, 0, 200), (False, 200, 500), (True, 500, 1000)]。