Pengjielee's blog

题目

给你两个有序整数数组 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

/**
 * @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) {
  const sorted = new Array(m + n).fill(0);

  let p1 = 0,
    p2 = 0,
    curr;
  while (p1 < m || p2 < n) {
    if (p1 === m) {
      curr = nums2[p2++];
    } else if (p2 === n) {
      curr = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      curr = nums1[p1++];
    } else {
      curr = nums2[p2++];
    }
    sorted[p1 + p2 - 1] = curr;
  }
  for (let i = 0; i < m + n; i++) {
    nums1[i] = sorted[i];
  }
};

Go实现

package main

import (
  "fmt"
)

func main() {
  nums1 := []int{1, 2, 3, 0, 0, 0}
  m := 3
  nums2 := []int{0, 1, 2}
  n := 3

  mergeArr(nums1, m, nums2, n)
  fmt.Println(nums1)

  nums1 = []int{1, 2, 3, 0, 0, 0}
  nums2 = []int{2, 5, 6}
  mergeArr2(nums1, m, nums2, n)
  fmt.Println(nums1)
}

/*
nums1 := []int{1, 2, 3, 0, 0, 0}
m := 3
nums2 := []int{0, 1, 2}
n := 3
*/
func mergeArr(nums1 []int, m int, nums2 []int, n int) {
  p := m - 1
  q := n - 1
  k := len(nums1) - 1
  for p >= 0 && q >= 0 {
    if nums1[p] > nums2[q] {
      nums1[k] = nums1[p]
      p -= 1
    } else {
      nums1[k] = nums2[q]
      q -= 1
    }
    k -= 1
  }

  for q >= 0 {
    nums1[k] = nums2[q]
    q -= 1
    k -= 1
  }
}

func mergeArr2(nums1 []int, m int, nums2 []int, n int) {
  for p := m + n; m > 0 && n > 0; p-- {
    if nums1[m-1] <= nums2[n-1] {
      nums1[p-1] = nums2[n-1]
      n--
    } else {
      nums1[p-1] = nums1[m-1]
      m--
    }
  }
  for ; n > 0; n-- {
    nums1[n-1] = nums2[n-1]
  }
}