[Algorithm] 6. Merge Two Sorted Arrays

时间:2021-11-08 12:22:21

Description

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?

Solution

 1     /**
 2      * @param A: sorted integer array A
 3      * @param B: sorted integer array B
 4      * @return: A new sorted integer array
 5      */
 6     vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
 7         // write your code here
 8         vector<int> res;
 9         int maxSize= A.size() > B.size() ? A.size() : B.size();
10         int index_a=0,index_b=0;
11         
12         for(int i=0; i<A.size()+B.size(); i++)
13         {
14             if(index_b==B.size()){
15                 for(int i=index_a; i<A.size(); i++)     res.push_back(A[i]);
16                 return res;
17             }
18             
19             if(index_a==A.size()){
20                 for(int i=index_b; i<B.size(); i++)     res.push_back(B[i]);
21                 return res;
22             }
23             
24             if (A[index_a] <= B[index_b]){
25                 res.push_back(A[index_a]);
26                 index_a++;
27             }else{
28                 res.push_back(B[index_b]);
29                 index_b++;
30             }
31         }
32         return res;
33     }

 

Tips

Select the minimum element from two arrays in every loop.