力扣(LeetCode) -- 算法第八十八题--合并两个有序数组

题目：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

示例 1:

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

示例 2:

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

思路一：

将两个数组合并后排序，调用arraycopy()方法，将指定源数组中的数组从指定位置复制到目标数组的指定位置。再使用sort()方法进行排序。

代码演示：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //调用arraycopy()方法，从源数组的0位置拷贝到目标数组的m位置，拷贝n各元素
        System.arraycopy(nums2, 0, nums1, m, n);
        //调用数组中的排序方法，对数组进行排序
        Arrays.sort(nums1);
    }

检查结果：

注释：

这道题最容易想到的方法就是直接调用方法，只用了nums1和nums2的数组，空间浪费资少。但是没有使用有序条件，使得数组一一取出重新排序，大大浪费了时间。

思路二：

思路一并没有使用题目中使用的条件“有序”,源数组按照了从小到大排序，利用有序，可以使用双指针，两个数组，从头部取出比较小的数字放在结果中，设立一个p1和p2作为头部指针，移动获取数据。

代码演示：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //控制指针从0开始。
        int p1 = 0, p2 = 0;
        //创建一个新数组存储排序后的数据
        int[] arr = new int[m + n];
        //创建一个数比较较小值，此题为有序数组
        int min;
        //循环指针移动比较元素，通过指针自增自减控制指针移动
        while (p1 < m || p2 < n) {
            //如果指针到最后一位，另一个数组的元素进入新数组
            if (p1 == m) {
                min = nums2[p2++];
            } else if (p2 == n) {
                min = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                min = nums1[p1++];
            } else {
                min = nums2[p2++];
            }
            //将较小的值存储进新数组里
            arr[p1 + p2 - 1] = min;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = arr[i];
        }

    }
}

检查结果：

注释：

思路二使用了双指针，从头到尾一一取出元素，减少了对比的时间，使用了中间变量，如果直接合并到数组nums1，nums1中元素可能在取出前被覆盖了。使用中间变量浪费了内存空间。

思路三：

如果直接合并到数组nums1中，nums1元素有可能在取出是被覆盖，造成元素丢失。据观察nums1的后半部分都是空的，可以直接覆盖不会影响结果，我们可以使用双指针，从后向前遍历，每次取两者之间最大的值放入到数组的最后。

代码演示：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //倒序，从最后一个开始
        int p1 = m - 1, p2 = n - 1;
        //数组长度
        int length = m + n - 1;
        int max;
        while (p1 != -1 || p2 != -1) {
            if (p1 == -1) {
                max = nums2[p2--];
            } else if (p2 == -1) {
                max = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                max = nums1[p1--];
            } else {
                max = nums2[p2--];
            }
            nums1[length--] = max;
        }
    }
}

检查结果：

注释：

此方法即使用题目中的“有序”，将两个数组元素一一对比取出，大大减少了对比的时间，又不用担心nums1元素在取出前被覆盖的问题，还不需要使用中间变量，减少了内存的使用。

感谢你的阅读，不足之处欢迎批评指正！