Merge Sorted Array

Question

• leetcode: Merge Sorted Array | LeetCode OJ

• lintcode: (6) Merge Sorted Array

  1. Given two sorted integer arrays A and B, merge B into A as one sorted array.
     2. 3. Example
     3. A = [1, 2, 3, empty, empty], B = [4, 5]
     4. 6. After merge, A will be filled as [1, 2, 3, 4, 5]
     5. 8. Note
     6. You may assume that A has enough space (size that is greater or equal to m + n)
     7. to hold additional elements from B.
     8. 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
    11.   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
    21.   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.         }
    21.   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;
    10.   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.         }
    22.   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).