两个数组的就地合并

Question

我们有一个大小为 m+n 的数组，其中 m 元素是 存在，按排序顺序，以及第二个大小为 n 的数组，同样按排序顺序。我们 希望它们都被排序并出现在第一个数组中。没有第三个数组 应该给予。

示例：

   1, 3, 55, 66, 77, _, _, _ 
   5, 9, 20 

答案是：

   1, 3, 5, 9, 20, 55, 66, 77 

Answer 1

进行常规合并，但相反，首先比较最大的数字，向后存储（反转）到第一个数组的末尾。这样，您要合并的元素就永远不会被覆盖（如果您想一下，就很容易看出这是有效的）。

Answer 2

    // merge the elements in B[] to A[], starting from the last one
    void merge(int A[], int m, int B[], int n) {
       // m-1 and n-1 represent the current element index in A[] and B[] respectively
      while (n > 0) { // there are still elements in B[] not merged
          if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
            A[m+n-1] = A[m-1]; // move current element of A[] to its right position
            --m; // decrease current element index of A[]
          }
         else { // current element in A[] <= current element in B[]
            A[m+n-1] = B[n-1]; // move current element in B[] to its right position
            --n; // decrease current element index of B[]
         }
      }
   }

Answer 3

将第一个数组的内容移动到第一个数组的末尾，使得空元素现在位于开头。然后照常将两个序列合并到第一个数组中。

Answer 4

就地基本上要求我们只使用“恒定”的内存量，这不会随着输入数组大小的不同而变化。然而，问题本身分配了与两个输入数组之一的大小相同的额外内存量，在最坏的情况下是 O(n) 内存。这基本上使得“就地”的想法变得毫无意义......

这个问题可能更好地表述为“无需额外内存的合并”，这是对其真实意图的更准确描述......