LeetCode.088.Merge Sorted Array 合并两个有序数组

题目描述

88 Merge Sorted Array
https://leetcode-cn.com/problems/merge-sorted-array/
面试题 10.01. Sorted Merge LCCI
https://leetcode-cn.com/problems/sorted-merge-lcci/

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

---

解题过程

如果直接把 nums2 从头到尾依次插入 nums1 的话，每次都需要移动 nums1 中的后续元素，时间复杂度为 O(mn)
由于 nums1 尾部预留了足够的空间，可以从后往前扫描，避免移动元素。
时间复杂度 O(m+n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (null == nums1 || null == nums2 || 0 == n) {
            return;
        }
        // 从后往前的指针
        int right = m + n - 1;
        int i =  m - 1, j = n - 1;
        // 注意 nums1 的长度 m 可能为0
        while (right >= 0 && j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[right--] = nums1[i--];
            } else {
                nums1[right--] = nums2[j--];
            }
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_088_MergeSortedArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_088_MergeSortedArray.java

---