题解 | #矩阵的最小路径和#

题目中给定的A看似是一个固定长度的静态数组，实际上长度是超过M的，说明其后有一些额外的空间。首先可以正向比较存储，定义一个m+n长度的数组用于逐步比较存储较小值。需要注意的就是需要边界判断。

import java.util.*;

public class Solution {
    /***
     * 正向，定义辅助数组逐个比较用于存储结果
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public void merge(int[] A, int m, int[] B, int n) {

        int[] res = new int[m + n];

        int i = 0, j = 0;
        while (i < m || j < n) {
            if (i == m) {
                res[i + j] = B[j++];
            } else if (j == n) {
                res[i + j] = A[i++];
            } else if (A[i] <= B[j]) {
                res[i + j] = A[i++];
            } else {
                res[i + j] = B[j++];
            }
        }
        // 送回给A 数组
        for (int k = 0; k < m + n; k++) {
            A[k] = res[k];
        }

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.merge(new int[]{1, 3, 5, 7}, 4, new int[]{3, 6, 9, 10}, 4);
    }
}

逆向双指针

不开辟额外空间，要保持从小到大的顺序，那么从后往前遍历，找最大的放到后面，就不用担心有些值会被覆盖掉了。

public class Solution {
    /***
     * 正向，定义辅助数组逐个比较用于存储结果
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1, j = n - 1, index = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i < 0) {
                A[index--] = B[j--];
            } else if (j < 0) {
                A[index--] = A[i--];
            } else if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.merge(new int[]{1, 3, 5, 7,0,0,0,0}, 4, new int[]{3, 6, 9, 10}, 4);
    }
}