88.合并两个有序数组

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，其中 nums1 有足够的空间容纳 nums2 的元素。请你将 nums2 合并到 nums1 中，使得合并后的数组同样按非递减顺序排列。

注意：

最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n。

示例：

int[] nums1 = new int[6]; // nums1的长度为6，其中前三个元素有值
nums1[0] = 1;
nums1[1] = 3;
nums1[2] = 5;

int[] nums2 = {2, 4, 6};
int m = 3;
int n = 3;

merge(nums1, m, nums2, n);

// 输出合并后的结果
System.out.println(Arrays.toString(nums1));

解法

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    // i指向nums1中有元素的最后一个位置
    int i = m - 1;
    // j指向nums2中的最后一个位置
    int j = n - 1;
    // k指向nums1的最后一个位置，即合并后的数组的最后一个位置
    int k = m + n - 1;

    // 从后往前比较并合并
    while (i >= 0 && j >= 0) {
        // 如果nums1中的元素大于nums2中的元素，将nums1中的元素放入合并后的数组中
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            // 如果nums2中的元素大于等于nums1中的元素，将nums2中的元素放入合并后的数组中
            nums1[k--] = nums2[j--];
        }
    }

    // 将nums2中剩余的元素复制到nums1中
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}