数据结构【数组】（六）：合并两个有序数组

Myth丶恋晨 2022-03-06 11:36 101阅读 0赞

> leetcode-88

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

**说明：**

*  初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
 *  你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

**示例：**

输入:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6],       n = 3
    
    输出: [1,2,2,3,5,6]

**题解：**

public static void main( String[] args ) {
            int[] a = {1, 3, 5, 7, 0, 0, 0, 0};
            int[] b = {2, 4, 6, 8};
            merge(a, 4, b, b.length);
            System.out.println(Arrays.toString(a));
        }
    
    
        /**
         * 合并两个有序数组
         *
         * @param a    数组a
         * @param aLng 数组a长度
         * @param b    数组b
         * @param bLng 数组b长度
         * @return void
         * @author lkf
         * @date 2019/3/18 17:42
         */
        public static void merge( int[] a, int aLng, int[] b, int bLng ) {
            int totalLength = aLng + bLng - 1;
            --aLng;
            --bLng;
            while (bLng >= 0) {
                System.out.println("aLength：" + aLng + "  a[aLength]：" + a[aLng] + "  bLength：" + bLng + "  b[bLength]：" + b[bLng]);
                a[totalLength--] = (aLng >= 0 && a[aLng] > b[bLng]) ? a[aLng--] : b[bLng--];
            }
        }

输出结果：

aLength：3  a[aLength]：7  bLength：3  b[bLength]：8
    aLength：3  a[aLength]：7  bLength：2  b[bLength]：6
    aLength：2  a[aLength]：5  bLength：2  b[bLength]：6
    aLength：2  a[aLength]：5  bLength：1  b[bLength]：4
    aLength：1  a[aLength]：3  bLength：1  b[bLength]：4
    aLength：1  a[aLength]：3  bLength：0  b[bLength]：2
    aLength：0  a[aLength]：1  bLength：0  b[bLength]：2
    [1, 2, 3, 4, 5, 6, 7, 8]

过程解析：

数组a：1 3 5 7 0 0 0 0
    数组b：2 4 6 8
    
    第一次：7 比 8 》 1 3 5 7 0 0 0 8
    第二次：7 比 6 》 1 3 5 7 0 0 7 8
    第三次：5 比 6 》 1 3 5 7 0 6 7 8
    第四次：5 比 4 》 1 3 5 7 5 6 7 8
    第五次：3 比 4 》 1 3 5 4 5 6 7 8
    第六次：3 比 2 》 1 3 3 4 5 6 7 8
    第七次：1 比 2 》 1 2 3 4 5 6 7 8