LeetCode.88 合并两个有序数组-一一网

这是我参与更文挑战的第28天，活动详情查看：更文挑战

题目描述：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例一

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

示例二

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
复制代码

提示

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
$10^9 <= nums1[i], nums2[i] <= 10^9$

思路分析

直接合并排序

这个没什么好说的吧，将两个数组合并后排序即可。如果用Java的话，合并可以使用 System.arraycopy 方法快速拷贝。

双指针法（从前往后）

我们再看一下题目会发现，这是两个已经排好序的数组，我们只需要每次从两个数组取出第一个数，然后进行比较，按照题目要求排序，很明显了，我们需要两个指针来分别指向两个数组的头部。

AC代码

直接合并

    class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        java.lang.System.arraycopy(nums2, 0, nums1, m, n)
        java.util.Arrays.sort(nums1)
    }
}
复制代码

双指针法

   class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        var nums1_copy = IntArray(m)
        java.lang.System.arraycopy(nums1, 0, nums1_copy, 0, m)
    
        var p1 = 0
        var p2 = 0
    
        var p = 0
        
        while ((p1 < m) && (p2 < n)) {
    
            nums1[p++] =  if (nums1_copy[p1] < nums2[p2]) {
                nums1_copy[p1++]
            } else {
                nums2[p2++]
            }
        }
        if (p1 < m) {
            java.lang.System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2)
        }
        if (p2 < n) {
            java.lang.System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2)
        }
        
    }
}
复制代码