数组与字符串之合并两个有序数组 | 春日游, 杏花吹满头

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

提示：

* -10^9 <= nums1[i], nums2[i] <= 10^9
* nums1.length == m + n
* nums2.length == n

示例

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出：[1,2,2,3,5,6]

分析

双指针从后向前遍历, 假设nums1是合并后的新数组, 遍历nums2, 当nums2中的元素大于nums1中元素的时候, push到nums1后面

代码

Python3

nums1_index = m - 1
nums2_index = n - 1
tail = m + n - 1

while(nums2_index >= 0 and nums1_index >= 0):
  if nums1[nums1_index] > nums2[nums2_index]:
    nums1[tail] = nums1[nums1_index]
    nums1_index -= 1
    tail -= 1
  else:
    nums1[tail] = nums2[nums2_index]
    nums2_index -= 1
    tail -= 1

JavaScript

function mergeTwoArray(nums1, m, nums2, n) {
  let nums1_index = m - 1
  let nums2_index = n - 1
  let tail = m + n - 1

  while (nums2_index >= 0) {
    // 当nums1[nums1_index]位置上的数大于nums2[nums2_index]位置上的数时
    if (nums1[nums1_index] > nums2[nums2_index]) {
      // nums1[tail]上的数为nums1[nums1_index]
      nums1[tail] = nums1[nums1_index]
      // nums1指针左移
      nums1_index--
      tail--
    } else {
      nums1[tail] = nums2[nums2_index]
      nums2_index--
      tail--
    }
  }
};

越界问题

在Python3中执行如下数据时会发生越界问题

[2, 0]
1
[1]
1

Python3

if n == 0:
  pass
elif m == 0:
  nums1[:n] = nums2[:n]
else:
  nums1_index = m - 1
  nums2_index = n - 1
  tail = m + m - 1
  while nums1_index >= 0 and nums2_index >= 0:
    if nums2[nums2_index] > nums1[nums1_index] :
      nums1[tail] = nums2[nums2_index]
      nums2_index -= 1
      tail -= 1
    else:
      nums1[tail] = nums1[nums1_index]
      nums1_index -= 1
      tail -= 1
  if nums1_index >= 0:
    pass
  if nums2_index >= 0:
    nums1[tail - nums2_index:tail + 1] = nums2[:nums2_index + 1]