面试题5（相关题目）

《剑指offer》面试题5：相关题目

题目：有2个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2，请实现一个函数，把A2中的所有数字插入到A1中，并且数组整体有序。

思路：从后往前遍历数组，例如数组A1={5,7,9,10,null,null,null,null...}，数组A2={1,2,3,8}，
A1的长度是n，有值部分的长度是len1=4，A2长度是len2=4。准备2个指针：p1和p2，p1指向A1有值部分的末尾（p1=3），p2指向A2末尾（p2=3），比较2指针指向的数的大小，如果p1指向的数大于或等于p2指向的数（例如：10>8），则将p1指向的数复制到数组A1的第p1+p2+1位上，然后p1左移一位；如果p1指向的数小于p2指向的数（例如：7<8），则将p2指向的数复制到数组A1的第p1+p2+1位上，然后p2左移一位。重复比较移动的过程，当p2越界（A2已遍历完）时，数组A1已整体有序；当p1越界（A1已遍历完）时，需要把数组A2的剩余部分拷贝至A1的头部，然后数组就A1是整体有序的。

代码如下：

public Integer[] merge(Integer[] arr1,Integer[] arr2) {
    if (arr1 == null && arr2 != null) {
        return arr2;
    }
    if (arr1 != null && arr2 == null) {
        return arr1;
    }
    if (arr1 == null && arr2 == null) {
        return null;
    }
    int len1 = 0;
    for (int i = 0;i < arr1.length;i++) {
        if (arr1[i] != null) {
            len1++;
        }
    }
    int p1 = len1 - 1;
    int p2 = arr2.length - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (arr1[p1] >= arr2[p2]) {
            arr1[p1 + p2 + 1] = arr1[p1--];
        } else {
            arr1[p1 + p2 + 1] = arr2[p2--];
        }
        while (p1 < 0 && p2 >= 0) {
            arr1[p2] = arr2[p2--];
        }
    }
    return arr1;
}