arrays - 如何从两个排序数组的交替元素生成所有可能的排序数组？

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

我不是在寻找代码，只要算法/伪代码就可以了。谢谢!

Answer 1

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

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

更新

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