LeetCode88. 合并两个有序数组｜刷题打卡

╰+攻爆jí腚メ 2022-11-05 08:44 189阅读 0赞

# 一、题目描述 #

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

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

**示例 1：**

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

**示例2：**

输入：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

# 二、思路分析 #

本题我们采用双指针法来解：

*  首先我们定义两个指针，各指向两个数组生效部分的尾部：  
    ![3091cf5bf5e92d06e22ab27a00a311b5.png][]
 *  每次只对指针所指的元素进行比较。取其中较大的元素，把它从 nums1 的末尾往前面填补：

![b05b048fe3ea9510dcc1b2d6e344bf81.png][]

*  再考虑其中一个数组提前遍历完的清空：
    
     *  如果提前遍历完的是 nums1 ，直接把 nums2 整个补到 nums1 前面去即可。
     *  如果提前遍历完的是 nums2，此时不必做任何额外的操作。

# 三、AC 代码 #

/**
     * @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) {
     // 初始化两个指针的指向，初始化 nums1 尾部索引k
        let i = m - 1, j = n - 1, k = m + n - 1
        // 当两个数组都没遍历完时，指针同步移动
        while(i >= 0 && j >= 0) {
            // 取较大的值，从末尾往前填补
            if(nums1[i] >= nums2[j]) {
                nums1[k] = nums1[i] 
                i-- 
                k--
            } else {
                nums1[k] = nums2[j] 
                j-- 
                k--
            }
        }
        
        // nums2 留下的情况，特殊处理一下 
        while(j>=0) {
            nums1[k] = nums2[j]  
            k-- 
            j--
        }
    };

# 四、总结 #

*  合并到nums1时，采用从后往前填补，可以避免值被覆盖的问题。

[3091cf5bf5e92d06e22ab27a00a311b5.png]: /images/20221023/b864bcbe068046ca93eae818d89d3a44.png
[b05b048fe3ea9510dcc1b2d6e344bf81.png]: /images/20221023/38587f08593f40c391609216e6ccc6da.png