Merge Sorted Array II

Question

  1. Merge two given sorted integer array A and B into a new sorted integer array.
  3. Example
  4. A=[1,2,3,4]
  6. B=[2,4,5,6]
  8. return [1,2,2,3,4,4,5,6]
  10. Challenge
  11. How can you optimize your algorithm
  12. 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
  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
  21.         # A has elements left
  22.         while i < aLen:
  23.             C.append(A[i])
  24.             i += 1
  26.         # B has elements left
  27.         while j < bLen:
  28.             C.append(B[j])
  29.             j += 1
  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;
  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.         }
  24.         // A has elements left
  25.         while (i < aLen) {
  26.             C.push_back(A[i]);
  27.             ++i;
  28.         }
  30.         // B has elements left
  31.         while (j < bLen) {
  32.             C.push_back(B[j]);
  33.             ++j;
  34.         }
  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;
  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.         }
  23.         // A has elements left
  24.         while (i < aLen) {
  25.             C.add(A.get(i));
  26.             i++;
  27.         }
  29.         // B has elements left
  30.         while (j < bLen) {
  31.             C.add(B.get(j));
  32.             j++;
  33.         }
  35.         return C;
  36.     }
  37. }

源码分析

分三步走，后面分别单独处理剩余的元素。

复杂度分析

遍历 A, B 数组各一次，时间复杂度 O(n), 空间复杂度 O(1).

Challenge

两个倒排列表，一个特别大，一个特别小，如何 Merge？此时应该考虑用一个二分法插入小的，即内存拷贝。