Merge Sorted Array

Question

  1. Given two sorted integer arrays A and B, merge B into A as one sorted array.
  3. Example
  4. A = [1, 2, 3, empty, empty], B = [4, 5]
  6. After merge, A will be filled as [1, 2, 3, 4, 5]
  8. Note
  9. You may assume that A has enough space (size that is greater or equal to m + n)
  10. to hold additional elements from B.
  11. The number of elements initialized in A and B are m and n respectively.

题解

因为本题有 in-place 的限制，故必须从数组末尾的两个元素开始比较；否则就会产生挪动，一旦挪动就会是 O(n^2) 的。
自尾部向首部逐个比较两个数组内的元素，取较大的置于数组 A 中。由于 A 的容量较 B 大，故最后 m == 0 或者 n == 0 时仅需处理 B 中的元素，因为 A 中的元素已经在 A 中，无需处理。

Python

  1. class Solution:
  2.     """
  3.     @param A: sorted integer array A which has m elements,
  4.               but size of A is m+n
  5.     @param B: sorted integer array B which has n elements
  6.     @return: void
  7.     """
  8.     def mergeSortedArray(self, A, m, B, n):
  9.         if B is None:
  10.             return A
  12.         index = m + n - 1
  13.         while m > 0 and n > 0:
  14.             if A[m - 1] > B[n - 1]:
  15.                 A[index] = A[m - 1]
  16.                 m -= 1
  17.             else:
  18.                 A[index] = B[n - 1]
  19.                 n -= 1
  20.             index -= 1
  22.         # B has elements left
  23.         while n > 0:
  24.             A[index] = B[n - 1]
  25.             n -= 1
  26.             index -= 1

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: sorted integer array A which has m elements,
  5.      *           but size of A is m+n
  6.      * @param B: sorted integer array B which has n elements
  7.      * @return: void
  8.      */
  9.     void mergeSortedArray(int A[], int m, int B[], int n) {
  10.         int index = m + n - 1;
  11.         while (m > 0 && n > 0) {
  12.             if (A[m - 1] > B[n - 1]) {
  13.                 A[index] = A[m - 1];
  14.                 --m;
  15.             } else {
  16.                 A[index] = B[n - 1];
  17.                 --n;
  18.             }
  19.             --index;
  20.         }
  22.         // B has elements left
  23.         while (n > 0) {
  24.             A[index] = B[n - 1];
  25.             --n;
  26.             --index;
  27.         }
  28.     }
  29. };

Java

  1. class Solution {
  2.     /**
  3.      * @param A: sorted integer array A which has m elements,
  4.      *           but size of A is m+n
  5.      * @param B: sorted integer array B which has n elements
  6.      * @return: void
  7.      */
  8.     public void mergeSortedArray(int[] A, int m, int[] B, int n) {
  9.         if (A == null || B == null) return;
  11.         int index = m + n - 1;
  12.         while (m > 0 && n > 0) {
  13.             if (A[m - 1] > B[n - 1]) {
  14.                 A[index] = A[m - 1];
  15.                 m--;
  16.             } else {
  17.                 A[index] = B[n - 1];
  18.                 n--;
  19.             }
  20.             index--;
  21.         }
  23.         // B has elements left
  24.         while (n > 0) {
  25.             A[index] = B[n - 1];
  26.             n--;
  27.             index--;
  28.         }
  29.     }
  30. }

源码分析

第一个 while 只能用条件与。

复杂度分析

最坏情况下需要遍历两个数组中所有元素，时间复杂度为 O(n). 空间复杂度 O(1).