Skip to main content

LeetCode 88 - Merge Sorted Array

  • Difficulty: Easy.
  • Related Topics: Array, Two Pointers, Sorting
  • Link: Leetcode

Problem​

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

Note:

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

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Constraints:​

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

Solution 1​

/**
 * @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 i = m - 1;
  let j = n - 1;
  let cur = m + n - 1;

  while (j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[cur] = nums1[i];
      i--;
    } else {
      nums1[cur] = nums2[j];
      j--;
    }
    cur--;
  }
};

Complexity:

  • Time complexity : O(m+n)
  • Space complexity : O(1)

Solution 2 : 將 nums2 的元素先放到 nums1，再排序 nums1 陣列​

var merge = function (nums1, m, nums2, n) {
  let index = 0;
  for (let i = m; i < m + n; i++) {
    nums1[i] = nums2[index];
    index++;
  }
  for (var j = 0; j < nums1.length; j++) {
    if (nums1[j] > nums1[j + 1]) {
      let temp = nums1[j];
      nums1[j] = nums1[j + 1];
      nums1[j + 1] = temp;
    }
  }
};