Java如何将一个数组的元素插入另一个数组并得到排序结果

代码问题分析 #

• 嵌套循环逻辑错误：外层遍历nums1预留空位的过程中，内层每次都会完整遍历整个nums2数组，nums1的每个空位会被依次赋值为nums2[0]、nums2[1]、nums2[2]，最终每个空位都会被覆盖为nums2的最后一个元素6，所以输出最后三位全是6。
• 缺少排序逻辑：即使正确把nums2元素填充到nums1的空位中，没有排序步骤也无法得到有序的合并结果。

正确实现方案 #

方案1：先填充再排序（写法简单，适合小数据量） #

import java.util.Arrays;

public class MergeArray {
    public static void main(String[] args) {
        int nums1[] = {1,2,3,0,0,0};
        int nums2[] = {2,5,6};
        int validLenOfNums1 = 3; // nums1原有有效元素的长度
        // 把nums2元素填充到nums1的预留空位
        for (int i = 0; i < nums2.length; i++) {
            nums1[validLenOfNums1 + i] = nums2[i];
        }
        // 对合并后的数组排序
        Arrays.sort(nums1);
        System.out.println(Arrays.toString(nums1));
    }
}

输出结果为你需要的[1, 2, 2, 3, 5, 6]。

方案2：双指针法（时间复杂度O(m+n)，高效利用两个数组本身有序的特性） #

示例中的nums1和nums2本身都是升序排列，可以从后往前遍历有效元素，直接把更大的元素放到nums1的末尾，不需要额外排序步骤：

import java.util.Arrays;

public class MergeArray {
    public static void main(String[] args) {
        int nums1[] = {1,2,3,0,0,0};
        int nums2[] = {2,5,6};
        int m = 3, n = 3; // m为nums1有效长度，n为nums2长度
        int p1 = m - 1; // 指向nums1最后一个有效元素
        int p2 = n - 1; // 指向nums2最后一个有效元素
        int p = m + n - 1; // 指向nums1最后一个空位

        while (p1 >= 0 && p2 >= 0) {
            // 把更大的元素放到nums1尾部空位，对应指针前移
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        // 处理nums2剩余的未放入元素
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
        System.out.println(Arrays.toString(nums1));
    }
}

内容的提问来源于stack exchange，提问作者ProgramCOder