algorithm - 在 O(n) 时间内给定特定顺序的两个集合的并集

Question

[Note: I am hoping this problem can be solved in O(n) time. If not, I am looking for a proof that it cannot be solved in O(n) time. If I get the proof, I'll try to implement a new algorithm to reach to the union of these sorted sets in a different way.]

考虑集合:

(1, 4, 0, 6, 3)
(0, 5, 2, 6, 3)

结果应该是:

(1, 4, 0, 5, 2, 6, 3)

请注意，排序集的并集问题很简单。这些也是排序集，但排序是由这些索引已解析的其他一些属性定义的。但是排序(无论它是什么)对两个集合都有效，即对于任何 i, j ∈ Set X如果i <= j ，然后在其他一些集合中 Y , 对于相同的 i, j, i <= j .

编辑: 很抱歉，我错过了一些非常重要的东西，我在下面的评论之一中已经提到了这一点——两个集合的交集不是空集，即两个集合有共同的元素。

Answer 1

将第一个集合中的每个项目插入到哈希表中。

遍历第二组中的每个项目，查找该值。

• 如果没有找到，将该项目插入到结果集中。
• 如果找到，将第一个集合中的所有项目插入到我们插入的最后一个项目之间，直到这个值。

最后，将第一个集合中的所有剩余项目插入到结果集中。

运行时间

预期 O(n)。

旁注

在给定约束的情况下，并集不一定是唯一的。

例如(1) (2)，结果集可以是(1, 2)或(2, 1)。

这个答案将选择 (2, 1)。

实现说明

显然，循环遍历第一个集合以查找最后插入的项目不会导致 O(n) 算法。相反，我们必须在第一个集合(而不是哈希表)中保留一个迭代器，然后我们可以简单地从迭代器拥有的最后一个位置继续。

这里是一些伪代码，假设两个集合都是数组(为简单起见):

for i = 0 to input1.length
   hashTable.insert(input1[i])

i = 0 // this will be our 'iterator' into the first set

for j = 0 to input2.length
   if hashTable.contains(input2[j])
      do
         output.append(input1[i])
         i++
      while input1[i] != input2[j]
   else
      output.append(input2[j])

while i < input.length
   output.append(input1[i])

for 循环中的 do-while 循环可能看起来很可疑，但请注意，该循环运行的每次迭代，我们都会增加 i，因此它总共可以运行 input1 .length 次。

示例

输入:

(1, 4, 0, 6, 8, 3)
(0, 5, 2, 6, 3)

哈希表:(1, 4, 0, 6, 8, 3)

然后，完成第二组。

查找0，找到了，于是将1,4,0​​插入到结果集中
(尚未插入第一组中的任何项目，因此从头开始插入所有项目，直到我们得到 0)。

查找5，没有找到，所以将5插入到结果集中。

查找2，没有找到，所以将2插入到结果集中。

查找6，找到了，所以将6插入到结果集中
(从第一组插入的最后一项是 0，因此只需要插入 6)。

查找3，找到了，所以将8, 3插入到结果集中
(从第一组插入的最后一项是 6，因此插入 6 之后的所有项目，直到我们得到 3)。

输出:(1, 4, 0, 5, 2, 6, 8, 3)