Question

Source

• lintcode: (64) Merge Sorted Array II

Merge two given sorted integer array A and B into a new sorted integer array.

Example
A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge
How can you optimize your algorithm
if one array is very large and the other is very small?

题解

上题要求 in-place, 此题要求返回新数组。由于可以生成新数组，故使用常规思路按顺序遍历即可。

Python

class Solution:
  #@param A and B: sorted integer array A and B.
  #@return: A new sorted integer array
  def mergeSortedArray(self, A, B):
    if A is None or len(A) == 0:
      return B
    if B is None or len(B) == 0:
      return A

    C = []
    aLen, bLen = len(A), len(B)
    i, j = 0, 0
    while i < aLen and j < bLen:
      if A[i] < B[j]:
        C.append(A[i])
        i += 1
      else:
        C.append(B[j])
        j += 1

    # A has elements left
    while i < aLen:
      C.append(A[i])
      i += 1

    # B has elements left
    while j < bLen:
      C.append(B[j])
      j += 1

    return C

C++

class Solution {
public:
  /**
   * @param A and B: sorted integer array A and B.
   * @return: A new sorted integer array
   */
  vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
    if (A.empty()) return B;
    if (B.empty()) return A;

    int aLen = A.size(), bLen = B.size();
    vector<int> C;
    int i = 0, j = 0;
    while (i < aLen && j < bLen) {
      if (A[i] < B[j]) {
        C.push_back(A[i]);
        ++i;
      } else {
        C.push_back(B[j]);
        ++j;
      }
    }

    // A has elements left
    while (i < aLen) {
      C.push_back(A[i]);
      ++i;
    }

    // B has elements left
    while (j < bLen) {
      C.push_back(B[j]);
      ++j;
    }

    return C;
  }
};

Java

class Solution {
  /**
   * @param A and B: sorted integer array A and B.
   * @return: A new sorted integer array
   */
  public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
    if (A == null || A.isEmpty()) return B;
    if (B == null || B.isEmpty()) return A;

    ArrayList<Integer> C = new ArrayList<Integer>();
    int aLen = A.size(), bLen = B.size();
    int i = 0, j = 0;
    while (i < aLen && j < bLen) {
      if (A.get(i) < B.get(j)) {
        C.add(A.get(i));
        i++;
      } else {
        C.add(B.get(j));
        j++;
      }
    }

    // A has elements left
    while (i < aLen) {
      C.add(A.get(i));
      i++;
    }

    // B has elements left
    while (j < bLen) {
      C.add(B.get(j));
      j++;
    }

    return C;
  }
}

源码分析

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

复杂度分析

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

Challenge

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