如何解決leetcode中合并兩個(gè)有序數(shù)組的問題

題目鏈接

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

題目描述

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

說明:

• 初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n。

• 你可以假設(shè) 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]

解題方案

思路

• 標(biāo)簽：從后向前數(shù)組遍歷

• 因?yàn)?code>nums1的空間都集中在后面，所以從后向前處理排序的數(shù)據(jù)會(huì)更好，節(jié)省空間，一邊遍歷一邊將值填充進(jìn)去

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

• 當(dāng)len1<0時(shí)遍歷結(jié)束，此時(shí)nums2中海油數(shù)據(jù)未拷貝完全，將其直接拷貝到nums1的前面，最后得到結(jié)果數(shù)組

• 時(shí)間復(fù)雜度：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) {
           // 注意--符號(hào)在后面，表示先進(jìn)行計(jì)算再減1，這種縮寫縮短了代碼
           nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
       }
       // 表示將nums2數(shù)組從下標(biāo)0位置開始，拷貝到nums1數(shù)組中，從下標(biāo)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) {
       // 注意--符號(hào)在后面，表示先進(jìn)行計(jì)算再減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數(shù)組從下標(biāo)0位置開始，拷貝到nums1數(shù)組中，從下標(biāo)0位置開始，長度為len2+1
   arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};

畫解