leetcode--Merge Sorted Array

1.题目描述

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:

You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

2.解法分析

这道题是归并排序的变种，我们知道，归并那一步应该是要有一个O(N+M)的辅助数组的，由于题目中说可以假设A有足够的空间来容纳A和B的内容，那么将A作为辅助数组就很合适，但是这必须要求A的前面n个位置必须先腾出来，以防止B的内容中最大的元素小于A中最小的元素这种极端情况。

class Solution {

public:

    void merge(int A[], int m, int B[], int n) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if(n==0)return;

      //将A原本的内容向右平移n位

        for(int i=m-1;i>=0;--i)

            A[i+n]=A[i];

        //然后以A为辅助空间，进行归并排序

        int i=n;

        int j=0;

        int k=0;

        while(i<=(m+n-1)&&j<n)

            if(A[i]<B[j])

                A[k]=A[i];i++;

            else

                A[k]=B[j];j++;

            k++;

        while(j<n)

            A[k]=B[j];k++;j++;

};

PS:补充说明，以上是第一次写的代码，其实不用腾空间，从大往小排就没问题了。