如何在o(1)空间复杂度中合并两个排序数组？

Question

我有两个排序数组，我必须将两个排序数组合并为一个，而不需要额外的空间？我正在检查这解决方案，但我无法理解它。

示例

Input: ar1[] = {10};
       ar2[] = {2, 3};
Output: ar1[] = {2}
        ar2[] = {3, 10}  

Input: ar1[] = {1, 5, 9, 10, 15, 20};
       ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
        ar2[] = {10, 13, 15, 20} 

Answer 1

我将为稍微简单一些的“两个数组已经在一个缓冲区中”的情况解决这个问题。

// requires: array is a pointer to a buffer of numbers,
// such that from [array, array+middle) is sorted, and [array+middle, array+length)
// is also sorted.
void merge_inplace( int* array, int length );

// This halves the number "gap", rounding up.  Unless the value was 1, in
// which case it returns 0.
int nextgap( int gap ) {
  if (gap==1) return 0;
  return (gap+1)/2;
}

void merge_inplace( int* array, int length ) {
  int gap = nextgap(length); // about half of length

  while (gap != 0)
  {
    int left = 0;
    int right = left+gap;
    while (right < length) {
      // ensure elements at left and right are in correct relative order:
      if (array[left] > array[right])
        std::swap(array[left], array[right]);
      // advance:
      ++left;
      ++right;
    }
    // repeat on a gap half-ish the size:
    gap = nextgap(gap);
  }
}

现在，在两个不同的数组上操作需要一些额外的工作/逻辑，但这主要是为了修改索引。

问题是，当两个数组被排序和相邻时，这个“合并很远，然后更近”的算法(它有子循环的日志长度计数；所以O(n lg n)步骤)就足够对其进行排序了。

Answer 2

在您的示例中，数组被重新排序。你需要这么做吗？

对于这个问题，您可以使用下一个算法：

1. 使用从0到array1长度的for循环
2. 比较array1和array2中的元素
3. 如果array2的一个元素小于array1的一个元素，那么交换它们
4. 遍历array2以找到一个更好的交换元素的位置

算法：

void reorder(std::vector<int>& arr1, std::vector<int>& arr2)
{
    for (size_t i = 0, j = 0; i < arr1.size(); )
    {
        if (arr1[i] < arr2[j])
        {
            i++;
            continue;
        }

        std::swap(arr1[i], arr2[j]);

        // find a better place for a swapped element in array 2
        for (size_t k = j, l = k+1; l < arr2.size(); k++, l++)
        {
            if (arr2[k] < arr2[l])
                break;
            std::swap(arr2[k], arr2[l]);
        }
    }
}

该算法可以改进。