java实现把两个有序数组合并到一个数组的实例

下面是Java实现把两个有序数组合并到一个数组的完整攻略。

1. 题目说明

有两个已排序的整数数组nums1和nums2，将nums2合并到nums1中，使得nums1成为一个有序数组。

注意：

• nums1和nums2的初始元素数量分别为m和n。
• nums1的长度足以容纳m+n个元素。

2. 思路分析

根据题目要求，我们需要将nums2中的所有元素按顺序插入到nums1中，并保持nums1中的有序性。因此，我们可以考虑从nums1和nums2的最后一个元素开始逐个比较，将较大的元素插入到nums1的末尾，这样可以避免覆盖nums1中尚未比较的元素。

具体步骤如下：

1. 定义两个指针p1和p2，分别指向nums1和nums2中的最后一个元素；
2. 定义变量end，表示合并后的数组中的最后一个元素的下标；
3. 从nums1和nums2的最后一个元素开始逐个比较，将较大的元素插入到nums1的末尾，然后将指针p1或p2向前移动；
4. 重复步骤3，直到nums2中的所有元素都插入到nums1中。

3. 代码实现

以下是Java实现把两个有序数组合并到一个数组的示例代码：

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 定义两个指针p1和p2，分别指向nums1和nums2中的最后一个元素
        int p1 = m - 1;
        int p2 = n - 1;
        // 定义变量end，表示合并后的数组中的最后一个元素的下标
        int end = m + n - 1;

        // 从nums1和nums2的最后一个元素开始逐个比较，将较大的元素插入到nums1的末尾
        while(p1 >= 0 && p2 >= 0) {
            if(nums1[p1] > nums2[p2]) {
                nums1[end--] = nums1[p1--];
            } else {
                nums1[end--] = nums2[p2--];
            }
        }

        // 将nums2中剩余的元素插入到nums1中
        while(p2 >= 0) {
            nums1[end--] = nums2[p2--];
        }
    }
}

4. 示例说明

下面以两个示例说明Java合并两个有序数组的实现。

示例一

输入：

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3

输出：

[1,2,2,3,5,6]

解释：

nums1的前三个元素为[1,2,3]，nums2的所有元素均小于等于3，因此将nums2中的元素[2,5,6]逐个插入到nums1中后，nums1变为一个有序数组[1,2,2,3,5,6]。

示例二

输入：

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [1,2,5], n = 3

输出：

[1,1,2,2,3,5]

解释：

nums1的前三个元素为[1,2,3]，nums2的元素[1,2]小于等于3，因此将这两个元素插入到nums1中后，nums1变为[1,1,2,2,3,0]，再将nums2中的元素[5]插入到nums1末尾，得到有序数组[1,1,2,2,3,5]。