1. 合并2个有序的数组
给你两个按 非递减顺序 排列的整数数组
nums1
和 nums2
，另有两个整数 m
和 n
，分别表示 nums1
和 nums2
中的元素数目。
请你 合并
nums2
到 nums1
中，使合并后的数组同样按 非递减顺序 排列。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [_1,2,2,3_,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
解法1：使用额外空间存储合并后的结果
双指针，找到2个数组中更小的放入到新的数组中；
最后将新数组赋值给
nums1
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums = [] i,j = 0,0 while i < m and j < n: if nums1[i] <= nums2[j]: nums.append(nums1[i]) i += 1 else: nums.append(nums2[j]) j += 1 nums.extend(nums1[i:m]) nums.extend(nums2[j:]) nums1[:] = nums
解法2：从后向前原地赋值
需要3个指针：
- i：指向nums1的m-1；
- j：指向nums2的n-1；
- k：指向nums1的最后一个元素；
找到
nums1
和nums2
中最大的值，从后开始放入nums1
；
要考虑到nums1、nums2已经遍历完的情况，如果用完了，则给一个最小值；（
-10**9
是题目中限定的数组最小值，并非int最小值）
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: i, j, k = m - 1, n - 1, m + n - 1 while k >= 0: temp1 = nums1[i] if i >= 0 else -10**9 temp2 = nums2[j] if j >= 0 else -10**9 if temp1 >= temp2: nums1[k] = temp1 i -= 1 else: nums1[k] = temp2 j -= 1 k -= 1
