[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 
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<
 
 
【代碼二】
 
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 
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<