题目

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

说明:

+　初始化 nums1 和 nums2 的元素数量分别为 m 和 n。

  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

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

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

题解

思路

  • 很多人已经讲得很清楚了
  • 从第一个数组的最后开始插入
  • 比较第一个数组和第二个数组的指针对应值谁大
  • 添加到数组的最后

代码

1
2
3
4
5
6
7
8
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        first, second, curr = m - 1, n - 1, len(nums1) - 1
        while curr != -1:
            if second < 0:return nums1
            elif first < 0:nums1[curr], second, curr = nums2[second], second - 1, curr - 1
            elif nums1[first] > nums2[second]:nums1[curr], first, curr = nums1[first], first - 1, curr - 1
            else: nums1[curr], second, curr = nums2[second], second - 1, curr - 1