Leetcode 第88題 Merge Sorted Array

題目：Merge Sorted Array

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

  Note:

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

題目分析：

• 一開始對題目的分析有錯，以為是直接将兩個數組按序合并起來
• 題目的含義是在數組1中取m個元素，在數組2中取n個元素，按序合并到數組1中

思路：

• 采用數組倒序放入數組的方式，優點是能夠不覆寫掉其他元素并且不用移動更多的元素
• 采用順序的方式也可以，隻是稍微複雜一些

代碼：

• C++：

//采用倒序的方式循環  并且題目的含義是從nums1中取出m個元素，在nums2中取出n個元素合并為新數組nums1；并不是直接nums1數組和nums2數組合并
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i,j,k;  
        for(i=m-,j=n-,k=m+n-;k>=;--k)  
        {  
            if(i>=&&(j<||nums1[i]>nums2[j]))
    //如果數組nums1沒有比較完，數組nums2比較完了或者數組nums1沒有比較完，數組nums2沒有比較完 數組nums2元素小于數組1元素值
    //那麼需要将數組1的值放入到後面  
            {  
                nums1[k]=nums1[i--];  
            }
    //如果數組1比較完了，或者是數組2的元素大于數組1的元素
            else nums1[k]=nums2[j--];  
        }  
    }
};
           

• 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) {
    var a=m-;
    var b=n-;
    for(var i=m+n-;i>=;--i)
    {
        if(a>= && b<)//說明a未比較完b已經比較完了那麼直接将所有的a都放入數組nums1中
        {
            nums1[i]=nums1[a--];
        }
        else if(a>= && b>= && nums2[b]<nums1[a])
        //說明a未比較完b未比較完并且數組1的值大于數組2的值那麼直接将a都放入數組nums1中
        {
            nums1[i]=nums1[a--];
        }
        else
        {
            nums1[i]=nums2[b--];
        }
    }
};
           

• Javascript：下面這個程式的作用是直接将數組1和數組2合并到數組1中

var merge = function(nums1, m, nums2, n) {
    var a=;
    var b=;
    for(var i=;i<m+n;i++)
    {
        if(a==m && b<n)
        {
            nums1.push(nums2[b]);
            b++;
        }
        else if(nums2[b]>nums1[i] && b<n)
        {
            a++;
        }
        else if(nums2[b]<nums1[i] && b<n)
        {
            nums1.splice(i,,nums2[b]);
            b++;
        }
    }
};
//注釋：預設m和n分别是數組的長度，是一開始了解題目有錯