如何从两个排序数组的备用元素生成所有可能的排序数组？

Question

我最近在一次采访中遇到了这个问题.我真的无法想出答案.我开始,从第一个数组中获取第一个元素,然后在另一个数组中找到比这个元素多的元素.但是,我的意思是,我不知道,无法真正形成解决方案.问题如下:

给定两个排序的数组A和B,生成所有可能的数组,使得第一个元素从A中取出,然后从B中取出,然后从A中取出,依此类推,直到数组耗尽为止.生成的数组应以B中的元素结尾.

Eg:
A = {10, 15, 25}
B = {1, 5, 20, 30}

The resulting arrays are:
  10 20
  10 20 25 30
  10 30
  15 20
  15 20 25 30
  15 30
  25 30

我不是在寻找一个代码,只需一个algo/pseduo-code就行了.谢谢!

Answer 1

如何使用带有 BFS 路径搜索的有向图。

1. 创建一个有向图，如果 B 中的元素更大，则从数组 A 中的元素到数组 B 中的每个元素创建有向边。反之亦然。如果 A 中的元素更大，则从数组 B 中的元素到数组 A 中的每个元素创建有向边。
2. 从 A 中选取一个元素
3. 然后使用BFS搜索生成所有可能的路径。
4. 每次路径包含来自 B 的元素时，将该子路径添加到您的解决方案路径列表中
5. 当 A 的所有元素都被用作搜索键时停止

更新

根据@MiljenMikic 的建议，您可以通过加速第 1 步来利用数组排序的事实。您不必搜索另一个数组中的所有元素来查找大于元素。只需跟踪最后找到的并在搜索时向前移动指针。

Answer 2

@dpmcmlxxvi提出的BFS解决方案很有意思.另外,我建议使用递归变体.一些基本要点:

• 你的递归函数的一个输入参数应该是一个布尔变量,它将指示你是应该从A还是从B添加一个元素; 您将在后续递归调用中替换此值

• 数组已排序 - 使用该信息!当你看到排序数组时,总是想到二进制搜索 - 在这种情况下,你应该递归传递最后添加的元素,然后在另一个数组中,二元搜索第一个元素大于最后一个元素

• 如果最后添加的元素来自B,则将当前工作数组添加到结果列表中