88.md

88. Merge Sorted Array

Leetcode link

解题思路

题目要求我们将两个升序的数组按照升序合并到第一个数组中

由于第一个数组的多余空间是在后面，所以我们考虑一种由后往前遍历的方法

首先我们需要定义一个变量 k，表示数组 1 的真实长度的最后一位

然后我们从数组 1 与数组 2 的有效位 m-1 与 n-1 由后往前遍历

如果数组 1 的数比数组 2 的大，则将其放到 k 的位置……以此类推

最后我们只需要再检查一次数组 2 有没有漏网之鱼就好，因为数组 1 剩下的部分恰好在排列好应该在的位置

C++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = m+n-1;
        m--;
        n--;
        
        while(m >= 0 && n >= 0) {
            if(nums1[m]>=nums2[n]) {
                nums1[k--] = nums1[m--];
            } else {
                nums1[k--] = nums2[n--];
            }
        }
        
        while(n>=0) {
            nums1[k--] = nums2[n--];
        }
    }
};

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 k = m+n-1;
    m--;
    n--;
    
    while(m>=0 && n>=0) {
        if(nums1[m]>=nums2[n]) {
            nums1[k--] = nums1[m--];
        } else {
            nums1[k--] = nums2[n--];
        }
    }
    
    while(n>=0) {
        nums1[k--] = nums2[n--];
    }
};