Merge Sorted Array

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 (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

 

解法一：从前往后，小的排最前。每次插入一个B，A需要整体后移。

class Solution {public:    void merge(int A[], int m, int B[], int n) {        int indA = 0;        int indB = 0;        int shift = 0;        while(indA < m+shift && indB < n)        {            if(A[indA] <= B[indB])                indA++;            else            {                for(int i = m-1+shift; i >= indA; i --)                    A[i+1] = A[i];                shift ++;                A[indA++] = B[indB++];            }        }        if(indA >= m+shift)        {            while(indB < n)                A[indA++] = B[indB++];        }    }};

 

解法二：从后往前，大的排最后。不需要多余的移动。

class Solution {public:    void merge(int A[], int m, int B[], int n) {        int indA = m-1;        int indB = n-1;        for(int i = m+n-1; i >= 0; i --)        {            if(indA < 0)            {
    // A finished                A[i] = B[indB --];            }            else if(indB < 0)            {
    // B finished                A[i] = A[indA --];            }            else            {                if(A[indA] >= B[indB])                    A[i] = A[indA --];                else                    A[i] = B[indB --];            }        }    }};