如何使用Java编写一个函数来将两个有序数组合并为一个有序数组？

题目要求编写一个函数，将两个有序数组合并为一个有序数组。这个问题看似简单，但可以发现需要处理的细节还是挺多的。接下来我将用1000字论述如何使用Java编写这个函数。

1.暴力合并

我们最基本的想法就是从头到尾扫描两个数组，比较元素大小，再将它们放入新的数组中。时间复杂度为O(n+m)，n和m分别为两个数组的长度。

代码实现如下：

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] nums = new int[m + n];
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            nums[k++] = nums1[i++];
        } else {
            nums[k++] = nums2[j++];
        }
    }

    while (i < m) {
        nums[k++] = nums1[i++];
    }

    while (j < n) {
        nums[k++] = nums2[j++];
    }

    System.arraycopy(nums, 0, nums1, 0, m + n);
}

这个代码实现还是比较简单的，不赘述。

2.双指针法

有一种方法被称为双指针法，它可以将空间复杂度降至O(1)。时间复杂度为O(n+m)，n和m分别为两个数组的长度。具体操作如下：

定义两个指针i和j分别指向两个数组的头部，比较两个指针所指向的元素大小，将较小的元素放入新的数组中，然后指针向后移动一位。需要注意的是，在一次比较中，如果有一个指针到达了数组的尾部，则直接将剩余数组中的元素插入到新数组中。

代码如下：

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] nums = new int[m + n];
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            nums[k++] = nums1[i++];
        } else {
            nums[k++] = nums2[j++];
        }
    }

    while (i < m) {
        nums[k++] = nums1[i++];
    }

    while (j < n) {
        nums[k++] = nums2[j++];
    }

    System.arraycopy(nums, 0, nums1, 0, m + n);
}

3.从后往前合并

其实还有一种更加巧妙的方法，可以将空间复杂度降至O(1)，不需要创建新数组。从后往前遍历，将较大的元素从nums1或nums2中复制到nums1的后面。时间复杂度O(n+m)，空间复杂度O(1)。

代码如下：

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;

    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }

    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

到这里，本文就结束了。从这个问题我们可以看到，对于同一个问题，有时候需要不同的方法去解决。希望这个文章可以对大家有所帮助。