1, 题目

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

  1. 输入:
  2. nums1 = [1,2,3,0,0,0], m = 3
  3. nums2 = [2,5,6],       n = 3
  4. 输出: [1,2,2,3,5,6]

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

2, 算法

  1. #scala
  2. object Solution {
  3.     def merge(nums1: Array[Int], m: Int, nums2: Array[Int], n: Int): Unit = {
  4.         var current = m
  5.         for (x <- nums2) {
  6.             nums1(current) = x
  7.             var j = current
  8.             while (j > 0 && nums1(j - 1) > nums1(j)) {
  9.                 val t = nums1(j - 1)
  10.                 nums1(j - 1) = nums1(j)
  11.                 nums1(j) = t
  12.                 j -= 1
  13.             }
  14.             current += 1
  15.         }
  16.     }
  17. }
  1. #python
  2. class Solution:
  3.     def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
  4.         """
  5.         Do not return anything, modify nums1 in-place instead.
  6.         """
  7.         for x in nums2:
  8.             nums1[m] = x
  9.             j = m
  10.             while j > 0 and nums1[j - 1] > nums1[j]:
  11.                 nums1[j - 1], nums1[j] = nums1[j], nums1[j - 1]
  12.                 j -= 1
  13.             m += 1