題目鏈接

https://leetcode-cn.com/problems/merge-sorted-array/

題目描述

給定兩個有序整數數組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。

說明:

• 初始化 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的空間都集中在后面，所以從后向前處理排序的數據會更好，節省空間，一邊遍歷一邊將值填充進去

• 設置指針len1和len2分別指向nums1和nums2的有數字尾部，從尾部值開始比較遍歷，同時設置指針len指向nums1的最末尾，每次遍歷比較值大小之后，則進行填充

• 當len1<0時遍歷結束，此時nums2中海油數據未拷貝完全，將其直接拷貝到nums1的前面，最后得到結果數組

• 時間復雜度：O(m+n)

代碼

• Java版本

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 = m - 1;
        int len2 = n - 1;
        int len = m + n - 1;
        while(len1 >= 0 && len2 >= 0) {
            // 注意--符號在后面，表示先進行計算再減1，這種縮寫縮短了代碼
            nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
        }
        // 表示將nums2數組從下標0位置開始，拷貝到nums1數組中，從下標0位置開始，長度為len2+1
        System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
    }
}

• JavaScript版本

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let len1 = m - 1;
    let len2 = n - 1;
    let len = m + n - 1;
    while(len1 >= 0 && len2 >= 0) {
        // 注意--符號在后面，表示先進行計算再減1，這種縮寫縮短了代碼
        nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
    }
    function arrayCopy(src, srcIndex, dest, destIndex, length) {
        dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length));
    }
    // 表示將nums2數組從下標0位置開始，拷貝到nums1數組中，從下標0位置開始，長度為len2+1
    arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};

畫解