📃 题目描述

题目链接：88. 合并两个有序数组 (opens new window)

🔔 解题思路

双指针

需要新开一个数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums2 == null || nums2.length == 0) {
            return ;
        }

        int[] nums3 = new int[m + n];

        int p1 = 0;
        int p2 = 0;
        int p3 = 0;

        while (p1 < m && p2 < n) {
            if (nums1[p1] < nums2[p2]) {
                nums3[p3 ++] = nums1[p1 ++];
            }
            else {
                nums3[p3 ++] = nums2[p2 ++];
            }
        }

        while (p1 < m) {
            nums3[p3 ++] = nums1[p1 ++];
        }
        while (p2 < n) {
            nums3[p3 ++] = nums2[p2 ++];
        }

        for (int i = 0; i < nums1.length; i ++) {
            nums1[i] = nums3[i];
        }
        
    }
}

逆向双指针

nums1 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1 的最后面

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums2 == null || nums2.length == 0) {
            return ;
        }

        // 从后往前遍历
        int p1 = m - 1;
        int p2 = n - 1;
        int tail = nums1.length - 1;
        while (p2 >= 0) {
            // p1 < 0 (p1 遍历完了但 p2 还没遍历完，直接把 p2 的剩余元素依次放到 nums1 的剩余空间就行了
            if (p1 < 0 || nums2[p2] >= nums1[p1]) {
                nums1[tail --] = nums2[p2 --];
            }
            else {
                nums1[tail --] = nums1[p1 --];
            }
        }
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：