力扣由浅至深 每日一题.16 合并两个有序数组

日复一日的生活里也会有新的快乐

                                  —— 24.3.27

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。（next[data]>=data）

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

方法一：直接合并后排序

最直观的方法是先将数组 nums2放进数组 nums1的尾部，然后直接对整个数组进行排序。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}

复杂度分析

时间复杂度：O((m+n)log⁡(m+n))。
排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log⁡(m+n))。

空间复杂度：O(log⁡(m+n))
排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log⁡(m+n))

方法二：双指针方法

方法一没有利用数组 nums1与 nums2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {   
# 如果数组1达到最大长度，则合并后总的数组3的新元素等于数组2p2++位置的元素
            if (p1 == m) {     
                cur = nums2[p2++];
            } else if (p2 == n) {    
# 如果数组2达到最大长度，则合并后总的数组3的新元素等于数组1p1++位置的元素
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
# 如果数组1，2都未达到最大长度，则合并后总的数组3的新元素等于数组1的p1位置元素和数组2p2位置元素的较小值
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
# 最终新数组长度发生改变
            sorted[p1 + p2 - 1] = cur;
        }
# 将合并后的新数组赋值到数组1中，不用返回，但是存在数组1的地址中
        for (int i = 0; i < m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

复杂度分析

时间复杂度：O(m+n)。
指针移动单调递增，最多移动 m+nm+nm+n 次，因此时间复杂度为 O(m+n)。

空间复杂度：O(m+n)。
需要建立长度为 m+nm+nm+n 的中间数组 sorted。

方法三：逆向双指针

双指针数组元素从后向前比较，我们在把大的值放入nums1中时，如果放的是nums1，则nums1空出一个位置 放的是nums2时，才会占位置，而空出的位置刚好是够nums2用的 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int a = m - 1, b = n - 1, c = m + n - 1;
        while (a >= 0 && b >= 0) {
            nums1[c--] =(nums1[a] > nums2[b] ? nums1[a--] : nums2[b--]);
        }

        while (a >= 0) {
            nums1[c--] = nums1[a--];
        }

        while (b >= 0) {
            nums1[c--] = nums2[b--];
        }
    }
}

复杂度分析

时间复杂度：O(m+n)。
指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

空间复杂度：O(1)。
直接对数组 nums1 原地修改，不需要额外空间。