如何从两个排序数组的备用元素生成所有可能的排序数组？ [英] How can I generate all possible sorted arrays from alternate elements of two sorted arrays?

问题描述

我最近在一次采访中遇到了这个问题。我真的无法给出答案。首先，从第一个数组中获取第一个元素，然后查找在另一个数组中有多少个元素大于该元素。但是，我的意思是，我不知道，无法真正形成解决方案。问题如下：

I recently encountered this question in an interview. I wasn't really able to come up with an answer to this. I started with, take first element from first array, and then find how many elements are greater than this element in the other array. But then, I mean, I don't know, couldn't really form a solution. The problem is as follows:

给出两个排序的数组A和B，生成所有可能的数组，使得第一个元素从A中取出，然后从B中取出，再从A中取出，依此类推以递增的顺序直到阵列用尽。

Given two sorted arrays A and B, generate all possible arrays such that first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. The generated arrays should end with an element from 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

我不是在寻找代码，只需算法/伪代码即可。谢谢！

I am not looking for a code, just an algo/pseduo-code would do fine. Thanks!

推荐答案

@dpmcmlxxvi提出的BFS解决方案很有趣。另外，我建议使用递归变量。一些基本要点：

BFS solution that @dpmcmlxxvi proposed is interesting. In addition, I would suggest a recursive variant. Some basic points:

• 递归函数的输入参数之一应该是布尔变量，它将指示您是否应该从中添加元素A或来自B;您将在随后的递归调用中替换该值



• 对数组进行排序-使用该信息！当您看到排序数组时，请始终想到 binary search -在这种情况下，您应该递归传递最后添加的元素，然后在另一个数组中对大于该最后一个元素的第一个元素进行二进制搜索

• one of the input arguments of your recursive function should be a boolean variable that will indicate whether you should add an element from A or from B; you will alternate this value in subsequent recursive calls

• arrays are sorted - use that information! When you see sorted arrays, always think of binary search - in this case you should recursively pass last added element and then, in the other array, binary search for the first element that is greater than that last element

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

if the last added element was from B, add the current working array to the resulting list

这篇关于如何从两个排序数组的备用元素生成所有可能的排序数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！