合并排序数组 II

题目

合并两个排序的整数数组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++];
        }
        
    }
}
Show Comments

Get the latest posts delivered right to your inbox.