LeetCode Merge Sorted Array 合并已排序的数组

时间:2021-01-20 04:08:50
 1 void merge(int A[], int m, int B[], int n) {
 2     int *a=A,*b=B;
 3     int i=0,j=0;
 4     if(n==0||m==0){        //针对特殊情况,比如A或B中无元素的情况
 5         if(n==0&&m!=0||n==0&&m==0)
 6             return;
 7         else
 8             for(i=0;i<n;i++)
 9                 A[i]=B[i];
10         return;
11     }
12     do{
13         while(*b>=*a&&i<m){
14             a++;
15             i++;    // i记录A中要插入的位置
16         }        
17         for(j=m;j>i;j--)    //A中从第i个开始往后移动一位
18             A[j]=A[j-1];
19         *a=*b;
20         m++;    //每循环一次,A中元素增加一个
21         b++;    //b指针往后取元素
22         n--;
23         a++;    //a指针也往后移一位,指向刚插进去的元素的后一个元素
24         i++;
25     }while(n>0);
26     return;
27 }

 

 

题意:将两个有序的数组(升序)合并为一个有序的数组(升序),将合并后的数组存储在A中。

注意:要考虑数组A或B中可能没有元素的情况。以数组作为实参传给形参传的是地址,所以在这个函数中操作数组A和B是直接对数组的直接操作,而m和n就只是盏中的一个实参副本,可随便改。

思路:把B中的元素从小到大逐个取出来,插入到A中去,要将合适位置后面的所有元素往后移一位。几乎每插一个进A都要移动A中的元素,除非特殊情况,如B中的最小元素比A中的最大元素要大,那么就不需要移动了。这个算法的效率还是不怎样的,应该有更好的算法,只是这个挺简洁的了。