Merge Sorted Array II · 數據結構與算法/leetcode/lintcode題解

# Merge Sorted Array II ### Source - lintcode: [(64) Merge Sorted Array II](http://www.lintcode.com/en/problem/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？此時應該考慮用一個二分法插入小的，即內存拷貝。