合并两个升序数组A和B到数组A

楚天乐 98 0 条

题目

给出两个有序的整数数组A(长度m)和B(长度n) ,请将AB数组合并到数组A中,变成一个有序的数组。

算法思路

  1. 合并后数据总长度m+n,最后一个元素的位置为A[m+n-1]
  2. 从前(下标0)向后(下标m-1,n-1)合并需要挪动后续元素,复杂度高。因此,我们从后向前合并。
  3. 如何合并?初始化当前合并下标lastPos = m+n-1, 当前A数组下标posA = m-1, 当前B数组下标posB = n-1
  4. 逐个比大小,A[posA]和B[posB]取较大元素,放入A[lastPos]。取A数组,则posA--; 取B数组则posB--。同时lastPos--
  5. 最后如果B数组有剩余,填入A数组即可

关于4和5,如果想问为什么这样就可以达到目的。注意观察,原始A数组中特定位置的数据,要么保持原位不变,要么会向后移动。因此,我们只需要取最大元素,放入lastPos即可

代码实现

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int posA = m-1;
        int posB = n-1;
        int lastPos = m + n - 1;

        while(posA >= 0 && posB >= 0){
            if( A[posA] >= B[posB] ){
                A[lastPos] = A[posA];
                posA --;
            }else{
                A[lastPos] = B[posB];
                posB --;
            }
            lastPos --;
        }

        while(posB >= 0){
            A[lastPos] = B[posB];
            posB -= 1;
            lastPos -= 1;
        }
    }
}


发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 57.561874389648 毫秒