arrays - 考虑到时间复杂度，如何将两个未排序的数组合并到另一个数组中

Question

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

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

标签： arrayssortingtime-complexity

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 const 因素中可以被移除，这会导致 O(n^2) 的运行时间。