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?
此题要求返回新数组。由于可以生成新数组，故使用常规思路按顺序遍历即可。
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 = , j = ;
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(1).
Challenge
两个倒排列表，一个特别大，一个特别小，如何 Merge？此时应该考虑用一个二分法插入小的，即内存拷贝。