用O（log（n m））最坏情况合并两个排序数组
我可以使用什么样的算法将两个排序数组合并为一个排序数组，最坏情况下的时间复杂度为O（log（m n）），其中n，m是数组的长度？我对算法的经验很少，但我检查了merge-sort，似乎合并步骤的时间复杂度是O（n）。在O（log（n））中是否有不同的合并方法？
编辑：我最初没有考虑过，但可能无法在O（log（n））中合并两个排序的数组？实际目标是找到两个排序数组的中值。有没有办法做到这一点而不合并它们？
我唯一的想法是，我读到合并两个二项式堆是O（log（n）），但将数组转换为二项式堆是O（n），我认为这样做行不通。
Edit2：我要发布一个新问题，因为我意识到合并永远不会足够快。相反，我认为我需要对每个数组执行二进制搜索，以找到log（n）中的中值。
共有3个答案
你需要合并数组。所以，不管怎样，你至少需要遍历2个数组，所以复杂度不能小于o（m n）
你可能在想选择算法。
对于排序后的数据结构，求中值是O（1）。对于未排序的数据结构（或将数据排序为两个逻辑分区的数据结构），运行时为O（n）。
你可能可以用大规模并行缩减算法来实现它，但我认为这在运行时分析方面是作弊的。
所以我不相信有一种算法能把它降低到O（n）（或者，在你的例子中，O（n m））
我不认为有一种算法会在O（log（n m））时间内合并两个数组。
当你仔细想想的时候，这是有道理的。如果您试图创建一个由n m个元素组成的新排序数组，则需要至少进行n m个拷贝。这是无法回避的。
我认为最好的方法是同时遍历每个数组，并在每次迭代时比较两个元素的值。如果一个小于另一个（如果您希望数组按降序排序），则将该元素复制到数组并增加该数组的索引指针，反之亦然。如果两个元素相同，您可以将它们都添加到新排序的数组中并增加两个指针。
继续，直到其中一个指针到达其各自数组的末尾，然后在其中一个指针到达后复制到另一个数组的其余部分。
应该是O（m n）
关于编辑，有一种方法可以在时间中找到两个独立数组的中值。
您可以首先找到两个排序数组（中间元素）的中间值，并对它们进行比较。如果它们相等，那么这就是中值。如果第一个中值大于第二个中值，则知道中值必须位于第一个数组的前半部分或第二个数组的后半部分，如果第一个中值小于第二个中值，则反之亦然。
此方法每次迭代都会将您的搜索空间减少一半，因此是log（n m）
-
问题内容： 给定两个排序数组，如下所示： 我希望输出为： 要么： 我知道我可以执行以下操作： 我只是想知道是否有一种更快的方法，因为我要处理的数组具有数百万个元素。 任何想法都欢迎。谢谢 问题答案： 由于您使用numpy，因此我怀疑bisec根本不会对您有所帮助。因此，我建议您做两件事： 千万 不能 使用，使用方法，而不是这种种取代阵列，避免了复制。 必须使用没有到位的。因此，不要手动使用逻辑。I
-
有人告诉我，在线性时间内，将两个已经排序的大小不同的数组A和B合并成一个数组C。 通过线性时间，我明白了这个算法的时间复杂度必须是O（n）。后来，我还被告知在合并数组时执行排序。 我的一个想法是创建一个算法，在两个数组中都有两个指针，指向最小的元素。指向的最小元素将进入新数组。当一个数组耗尽时，另一个数组的剩余元素将复制到新数组中。 由于几个月前我刚开始编程，我发现这很难实现，因此我决定执行合并排
-
问题是== 将nums1和nums2合并到一个按非递减顺序排序的数组中。 最终排序的数组不应由函数返回，而应存储在数组 nums1 中。为了适应这种情况，nums1 的长度为 m n，其中前 m 个元素表示应合并的元素，最后 n 个元素设置为 0 并应忽略。nums2 的长度为 n。 我的代码中有什么错误？？？ 您的意见 我的产出 预期产出
-
我知道类似的问题也有人问过，我也研究过很多网站。我已经尝试使用一些答案，但我的代码仍然不能工作。 我正在经历以前的作业，以帮助建立我的Java知识。请原谅我的代码中的任何错误，我还在学习Java。 假设两个输入数组中的元素都按非递减顺序排序（例如[0,1,2,2]和[1,2,3,3,4,5])。返回的“合并”数组必须保留此属性（例如[0,1,1,2,2,2,3,3,4,5])。 输入和输出都允许重
-
本文向大家介绍手写代码：合并两个排序数组相关面试题，主要包含被问及手写代码：合并两个排序数组时的应答技巧和注意事项，需要的朋友参考一下 参考回答：
-
问题内容： 这是在采访中问我的，这是我提供的解决方案： 有没有更有效的方法可以做到这一点？ 编辑：更正的长度方法。 问题答案： 稍有改进，但是在主循环之后，当到达另一个输入数组的末尾时，可以用来复制其中一个输入数组的结尾。但是，那不会改变你解决方案的性能特征。