题目

合并两个排序的整数数组A和B变成一个新的数组。你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。http://www.lintcode.com/zh-cn/problem/merge-sorted-array/

分析

既然A有足够的空间，那么只要把B中的元素归并到A中即可。由于A、B都是有序数组，通过两个游标，将B中的元素插入到A中，流程如下：

• 若A当前的游标指向的元素小于等于B，则A的游标向前滑动
• 若A当前的游标指向的元素大于B，则将A数组中从游标当前位置开始往后的元素全部向后移动一位，再将B数组中的游标指向元素拷贝到A的当前游标位置，同时A、B的游标向后移动
• 当B游标抵达数组末尾时，合并结束
• 有可能出现A的游标已经抵达末尾，但B的游标仍然未到末尾，此时直接将所有B中剩余元素逐一插入到A的游标位置

代码

class Solution {
    
       void moveForward(int[] A, int start, int count){
        for(;count >0 ; count--){
            A[start+count] = A[start+count-1];
        }
    }
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        // write your code here
        int i = 0, j = 0;
        int total = m;
        for(;j < n && i < total;){

            if(A[i] <= B[j]){
                i++;
            }else{
                moveForward(A, i, total-i);
                A[i++] = B[j++];
                total++;
            }
            
        }
        
        for( ; j < n ; ){
            A[i++] = B[j++];
        }
        
    }
}