Description
Merge two given sorted integer array A and B into a new sorted integer array.
Have you met this question in a real interview?
Yes
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?
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) { int lenA = A.size(); int lenB = B.size(); vector<int> C(lenA + lenB); int i = 0; int j = 0; int k = 0; for (i = 0, j = 0, k = 0; i < lenA && j < lenB;) { if (A[i] < B[j]) { C[k++] = A[i++]; } else { C[k++] = B[j++]; } } while (i < lenA) { C[k++] = A[i++]; } while (j < lenB) { C[k++] = B[j++]; } return C; } };思路:
1、最经典简单的双指针解法。