从数组列表中找到包含每个数组元素的最短序列长度

Question

这里有一个问题：

假设我们有以下数组：

[1,2,9]
[3,6,7]
[4,11]
[8,10,12]

数组中的元素是唯一且有序的。任务是找到包含每个数组至少一个元素的最短序列长度，但这些元素应该依次排列（不能有间隔，例如[1,3]不行），并且还要保持有序。因此，在这种情况下，答案是：

5 => [7,8,9,10,11]

有没有更高效的方法来完成这个任务？

- Oleksii Duzhyi

Answer 1

您可以使用双指针算法（很抱歉我没有找到任何参考资料）。其复杂度为O(nlogn)，其中n是所有数组中元素的总和。

首先，将所有元素放入一个一维数组中，每个元素都带有数组索引。就像这样：

struct A{
    int value;
    int array_id;
};

然后，按值(O(nlogn))对元素进行排序。我们的问题变成了查找覆盖所有数组的最短连续序列。这可以通过双指针算法完成。复杂度为O(n)。

因此，总复杂度为O(nlogn)。

- throwit

Answer 2

以下是解决方案：

1. 列出条目。
2. 将最小范围初始化为MAX_INT。
3. 保持3个指针/索引p1、p2和p3，它们分别指向列表L1、L2和L3的第一个元素。
4. 找到由p1、p2和p3指向/索引的最大值和最小值。
5. 在步骤3中发现的最大值和最小值之差是当前范围。如果发现更小，请将其与smallest_range进行比较并更新。
6. 增加在步骤3中找到的最小值的指针/索引。
7. 重复步骤3到5，直到最小值的指针/索引在范围内。

还可以查看此讨论。其中还包含C++和Java代码。

- Gor

---

我想提醒的是使用最小二进制堆，并不确定数组的确切数量，假设有n个数组。 - Oleksii Duzhyi