Merge Sorted Array II

Question

• lintcode: (64) Merge Sorted Array II

  1. Merge two given sorted integer array A and B into a new sorted integer array.
     2. 3. Example
     3. A=[1,2,3,4]
     4. 6. B=[2,4,5,6]
     5. 8. return [1,2,2,3,4,4,5,6]
     6. 10. Challenge
     7. How can you optimize your algorithm
     8. if one array is very large and the other is very small?

題解

上題要求 in-place, 此題要求返回新陣列。由於可以生成新陣列，故使用常規思路按順序遍歷即可。

Python

  1. class Solution:
    2.     #@param A and B: sorted integer array A and B.
    3.     #@return: A new sorted integer array
    4.     def mergeSortedArray(self, A, B):
    5.         if A is None or len(A) == 0:
    6.             return B
    7.         if B is None or len(B) == 0:
    8.             return A
    9.   10.         C = []
    11.         aLen, bLen = len(A), len(B)
    12.         i, j = 0, 0
    13.         while i < aLen and j < bLen:
    14.             if A[i] < B[j]:
    15.                 C.append(A[i])
    16.                 i += 1
    17.             else:
    18.                 C.append(B[j])
    19.                 j += 1
    20.   21.         # A has elements left
    22.         while i < aLen:
    23.             C.append(A[i])
    24.             i += 1
    25.   26.         # B has elements left
    27.         while j < bLen:
    28.             C.append(B[j])
    29.             j += 1
    30.   31.         return C

C++

  1. class Solution {
    2. public:
    3.     /**
    4.      * @param A and B: sorted integer array A and B.
    5.      * @return: A new sorted integer array
    6.      */
    7.     vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
    8.         if (A.empty()) return B;
    9.         if (B.empty()) return A;
    10.   11.         int aLen = A.size(), bLen = B.size();
    12.         vector<int> C;
    13.         int i = 0, j = 0;
    14.         while (i < aLen && j < bLen) {
    15.             if (A[i] < B[j]) {
    16.                 C.push_back(A[i]);
    17.                 ++i;
    18.             } else {
    19.                 C.push_back(B[j]);
    20.                 ++j;
    21.             }
    22.         }
    23.   24.         // A has elements left
    25.         while (i < aLen) {
    26.             C.push_back(A[i]);
    27.             ++i;
    28.         }
    29.   30.         // B has elements left
    31.         while (j < bLen) {
    32.             C.push_back(B[j]);
    33.             ++j;
    34.         }
    35.   36.         return C;
    37.     }
    38. };

Java

  1. class Solution {
    2.     /**
    3.      * @param A and B: sorted integer array A and B.
    4.      * @return: A new sorted integer array
    5.      */
    6.     public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
    7.         if (A == null || A.isEmpty()) return B;
    8.         if (B == null || B.isEmpty()) return A;
    9.   10.         ArrayList<Integer> C = new ArrayList<Integer>();
    11.         int aLen = A.size(), bLen = B.size();
    12.         int i = 0, j = 0;
    13.         while (i < aLen && j < bLen) {
    14.             if (A.get(i) < B.get(j)) {
    15.                 C.add(A.get(i));
    16.                 i++;
    17.             } else {
    18.                 C.add(B.get(j));
    19.                 j++;
    20.             }
    21.         }
    22.   23.         // A has elements left
    24.         while (i < aLen) {
    25.             C.add(A.get(i));
    26.             i++;
    27.         }
    28.   29.         // B has elements left
    30.         while (j < bLen) {
    31.             C.add(B.get(j));
    32.             j++;
    33.         }
    34.   35.         return C;
    36.     }
    37. }

源碼分析

分三步走，後面分別單獨處理剩餘的元素。

複雜度分析

遍歷 A, B 陣列各一次，時間複雜度 O(n), 空間複雜度 O(1).

Challenge

兩個倒排列表，一個特別大，一個特別小，如何 Merge？此時應該考慮用一個二分法插入小的，即記憶體拷貝。