[LeetCode]88.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 andn respectively.

【分析】

无

【代码】

/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 88.Merge Sorted Array
*   来源：https://oj.leetcode.com/problems/merge-sorted-array/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if(n <= 0){
            return;
        }//if
        int indexA = 0,indexB = 0;
        while(indexA < m && indexB < n){
            // B数组元素插入A数组中
            if(A[indexA] >= B[indexB]){
                // 后移一位
                for(int i = m-1;i >= indexA;i--){
                    A[i+1] = A[i];
                }//for
                A[indexA] = B[indexB];
                m++;
                indexB++;
            }//if
            indexA++;
        }//while
        // 如果B数组还没有遍历完
        while(indexB < n){
            A[indexA++] = B[indexB++];
        }//while
    }
};

int main() {
    Solution solution;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int m = 5;
    int n = 6;
    solution.merge(A,m,B,n);
    // 输出
    for(int i = 0;i < 11;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}

【代码二】

The idea is to go from the last indexes of both arrays, compare and put elements from either A or B to the final position, which can easily get since we know that A have enough space to store them all and we know size of A and B. Please refer to the comments for details.

/*********************************
*   日期：2015-01-05
*   作者：SJF0115
*   题目: 88.Merge Sorted Array
*   来源：https://oj.leetcode.com/problems/merge-sorted-array/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
using namespace std;

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        if(n <= 0){
            return;
        }//if
        int indexA = m-1,indexB = n-1,cur = m + n -1;
        // AB数组从后往前扫描
        while(indexA >= 0 && indexB >= 0){
            if(A[indexA] < B[indexB]){
                A[cur--] = B[indexB--];
            }//if
            else{
                A[cur--] = A[indexA--];
            }//else
        }//while
        // 如果B数组没有遍历完
        while(indexB >= 0){
            A[cur--] = B[indexB--];
        }//while
    }
};

int main() {
    Solution solution;
    int A[] = {1,2,4,7,9};
    int B[] = {3,5,8,10,11,12};
    int m = 5;
    int n = 6;
    solution.merge(A,m,B,n);
    // 输出
    for(int i = 0;i < 11;i++){
        cout<<A[i]<<" ";
    }
    cout<<endl;
}