[LeetCode]88. 合并两个有序数组(Merge Sorted Array)

题目描述

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 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]

解题思路

需要注意的是 nums1 后面的位置大于或者等于 nums2 的长度,可能为 0 或者 None。所以考虑从后往前遍历两个数组,依次把较大的那一个数字更新到 nums1 中,再调整下标即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# 从后往前遍历两个数组,依次加入 nums1 后面的位置
while n:
if m and nums1[m - 1] > nums2[n - 1]:
nums1[m + n - 1] = nums1[m - 1]
m -= 1
else:
nums1[m + n - 1] = nums2[n - 1]
n -= 1