牛课题霸NC22解析Java描述

题目

链接地址
给出两个有序的整数数组A和B，其中A足够大，合并两个数组至A中，使得合并后仍然有序。

解析

思路：

有点像归并排序中合并两个排序数组，但是这里有一点不同，就是A数组范围够大，因此我们可以不开辟额外的数组来存储结果。
从前往后归并如果在原数组上进行，会出现元素覆盖的情况，考虑从后往前原地归并，这样就不会出现该问题。

Java描述

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int p = m + n - 1;
        while(i >= 0 && j >= 0){
            A[p--] = A[i] >= B[j] ? A[i--] : B[j--]; 
        }
        while(j >= 0){A[p--] = B[j--];}
    }
}