如何在考虑时间复杂度的情况下将两个未排序的数组合并到另一个数组中

Question

>我有两个/更多的数组。我想形成一个新数组，该数组是从两个/多个数组中排序的。 我不想合并数组并在以后排序。我想在旅途中得到它。 考虑了时间复杂度。

任何编程语言/算法都可以。

Answer 1

所以基本上你需要为新数组中的每个位置找到最小的剩余值。 输入是带有 n 和 m 元素的数组 a 和 b。在两个数组中查找最小值。比较这两个值，并将较小的值设置为其数组中的最大值，以防止再次找到它。在 c 中设置最小值。

伪代码：

merge(a[n],b[m]){
c[n+m];
for (i = 0, i < n+m; i++){
aMin = getMinValue(a);
bMin = getMinValue(b);
if(aMin < bMin) setMinValueToMax(a,aMin)
else setMinValueToMax(b,bMin)
c[i] = min(aMin,bMin)
}
return c;
}

这里 n 是较大数组的大小。 GetMinValue 将以 O(n( 格式运行，只需遍历所有元素即可。如果您不保存索引，SetMinValueToMax 也将在 O(n( 中运行。for 循环将以 O(n( 为单位。for 的主体是 0(3n( (2 x getMinValue + setMinValueToMax(。在大 O 常量因子中可以去除，这导致运行时间为 O(n^2(。