LeetCode 88 _ 合并两个有序数组

1. 题目描述

2. 代码_解法1

1 class Solution:
2     def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
3         """
4         Do not return anything, modify nums1 in-place instead.
5         """
6         nums1[:] = sorted(nums1[:m] + nums2)

思想: 先拼接2个数组, 再排序.

解法2

 1 class Solution:
 2     def merge(self, nums1: 'List[int]', m: int, nums2: 'List[int]', n: int) -> None:
 3         """
 4         Do not return anything, modify nums1 in-place instead.
 5         """
 6         i,j,k = m-1,n-1,len(nums1)-1
 7         while i >=0 and j >= 0:
 8             if nums1[i] >= nums2[j]:
 9                 nums1[k] = nums1[i]
10                 i -= 1
11                 k -= 1
12             else:
13                 nums1[k] = nums2[j]
14                 j -= 1
15                 k -= 1
16         while j >= 0:
17             nums1[k] = nums2[j]
18             j -= 1
19             k -= 1

思想: 通过对比2个数组的元素大小, 然后更新数组nums1.

也就是通过从后往前, 通过两个数组 i, j 的索引和最终nums1的索引k来更新nums1.