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 只能用條件與(conditional AND)。

複雜度分析

最壞情況下需要遍歷兩個陣列中所有元素，時間複雜度為 O(n). 空間複雜度 O(1).