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

Question

这里有个问题：

假设我们有以下数组：

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

数组中的项目是唯一且有序的。任务是找到最短的序列长度，它将包含每个数组的至少一个元素，但这些元素应该一个接一个（没有间隙，不能是 [1,3]）并且也是有序的。所以在这种情况下答案是：

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

有什么有效的方法吗？

Answer 1

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

首先，将所有元素放入一维数组中，为每个元素提供数组索引。就这样，

struct A{
    int value;
    int array_id;
};

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

所以总复杂度是 O(nlogn)。

Answer 2

这很容易解决，如下所示。

1. 列表项
2. 初始化smallest_range为MAX_INT
3. keep 3 pointers/index p1、p2 和 p3 分别指向列表 L1、L2 和 L3 的第一个元素。
4. 通过p1,p2,p3求最大值和最小值pointed/indexed
5. 第3步发现的最大值和最小值之差就是当前范围。将它与 smallest_range 进行比较并更新它，如果发现更小。
6. 增加第 3 步中找到的最小值 pointer/index。
7. 重复步骤 3 到 5，直到 pointer/index 的最小值在范围内。

另请查看 this 讨论。这是关于你的问题。 在那里你也可以找到 c++ 和 java 代码