6.合并排序数组-创新互联

合并两个排序的整数数组A和B变成一个新的数组。6.合并排序数组

样例

成都创新互联公司专注于唐山网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供唐山营销型网站建设,唐山网站制作、唐山网页设计、唐山网站官网定制、成都小程序开发服务,打造唐山网络公司原创品牌,更为您提供唐山网站排名全网营销落地服务。

给出A=[1,2,3,4],B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]

先上一个无脑的,可以AC

1 vector mergeSortedArray(vector &A, vector &B) {
2 // write your code here3 for(int i=0;i

其实这个题是面试场景出现的话,完全可以先弄一个暴力的出来,后面再慢慢优化,这也是一个思路的过程

下面这一个就是很常规的了,就是申请了一个新数组,空间复杂度高一些

 1 vector mergeSortedArray(vector &A, vector &B) {
 2 // write your code here 3         vector result(A.size()+B.size(), 0);  
 4 int i = 0, j = 0;  
 5 int k = 0;  
 6 while (i < A.size() && j < B.size())  
 7         {  
 8  if (A[i] > B[j])  
 9             {  
10                 result[k++] = B[j++];  
11             } 
12  else  
13             {  
14                 result[k++] = A[i++];  
15             }  
16         }  
17 while (i < A.size())  
18         {  
19             result[k++] = A[i++];  
20         }  
21 while (j < B.size())  
22         {  
23             result[k++] = B[j++];  
24         }  
25 return result;  
26     }

名称栏目:6.合并排序数组-创新互联
网站路径:http://pwwzsj.com/article/dscece.html