描述

給出一個整數(shù)數(shù)組 和有序的整數(shù)數(shù)組 ，請將數(shù)組 合并到數(shù)組 中，變成一個有序的升序數(shù)組
注意：
1.可以假設(shè) 數(shù)組有足夠的空間存放 數(shù)組的元素， 和 中初始的元素數(shù)目分別為 和 ，的數(shù)組空間大小為 +
2.不要返回合并的數(shù)組，返回是空的，將數(shù)組 的數(shù)據(jù)合并到里面就好了
3.數(shù)組在[0,m-1]的范圍也是有序的

例1:
A: [4,5,6,0,0,0]，m=3
B: [1,2,3]，n=3
合并過后A為:
A: [1,2,3,4,5,6]

解法一：

    /**
     * 兩個有序數(shù)組合并
     * 逆向解法
     *
     * @param A 數(shù)組A
     * @param B 數(shù)組B
     * @param m 數(shù)組A的元素長度
     * @param n 數(shù)組B的元素長度
     */
    private void mergeArray(int[] A, int[] B, int m, int n) {

        int A_index, B_index, A_end_index;

        A_index = m - 1;
        B_index = n - 1;
        A_end_index = m + n - 1;

        while (A_index >= 0 || B_index >= 0) {
            if (A_index >= 0 && B_index >= 0 && A[A_index] > B[B_index]) {
                A[A_end_index] = A[A_index];
                A_index--;
                A_end_index--;
            } else {
                if (B_index >= 0) {
                    A[A_end_index] = B[B_index];
                    B_index--;
                    A_end_index--;
                }
            }
            if (A_index < 0) {
                if (B_index >= 0) {
                    A[A_end_index] = B[B_index];
                    B_index--;
                    A_end_index--;
                }
            }
            if (B_index < 0) {
                if (A_index >= 0) {
                    A[A_end_index] = A[A_index];
                    A_index--;
                    A_end_index--;
                }
            }
        }
    }

解法二：

    /**
     * 兩個有序數(shù)組合并
     * 正向解法
     *
     * @param A 數(shù)組A
     * @param B 數(shù)組B
     * @param m 數(shù)組A的元素長度
     * @param n 數(shù)組B的元素長度
     */
    public void mergeArray2(int[] A, int[] B, int m, int n) {
        // 分別用來記錄 A和B的增量索引
        int p1 = 0, p2 = 0;

        /*
            int[] A = {4,5,6, 0, 0, 0};
            int[] B = {1,2,3};
         */
        // 新創(chuàng)建一個數(shù)組
        int[] tem = new int[m + n];

        while (p1 < m || p2 < n) {
            int cur;
            if (p1 == m) {
                // 當(dāng)A中的元素已經(jīng)遍歷完了
                cur = B[p2++];
            } else if (p2 == n) {
                // 當(dāng)B中的元素已經(jīng)遍歷完了
                cur = A[p1++];
            } else if (A[p1] < B[p2]) {
                cur = A[p1++];
            } else {
                cur = B[p2++];
            }
            tem[p1 + p2 - 1] = cur;
        }

        for (int i = (m + n - 1); i >= 0; i--) {
            A[i] = tem[i];
        }

    }