0088. 合并两个有序数组 #
- 标签:数组、双指针、排序
- 难度:简单
题目大意 #
描述:给定两个有序数组 nums1
、nums2
。
要求:将 nums2
合并到 nums1
中,使 nums1
成为一个有序数组。
说明:
- 给定数组
nums1
空间大小为m + n
个,其中前m
个为nums1
的元素。nums2
空间大小为n
。这样可以用nums1
的空间来存储最终的有序数组。 - $nums1.length == m + n$。
- $nums2.length == n$。
- $0 \le m, n \le 200$。
- $1 \le m + n \le 200$。
- $-10^9 \le nums1[i], nums2[j] \le 10^9$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:快慢指针 #
- 将两个指针
index1
、index2
分别指向nums1
、nums2
数组的尾部,再用一个指针index
指向数组nums1
的尾部。 - 从后向前判断当前指针下
nums1[index1]
和nums[index2]
的值大小,将较大值存入num1[index]
中,然后继续向前遍历。 - 最后再将
nums2
中剩余元素赋值到num1
前面对应位置上。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m + n)$。
- 空间复杂度:$O(m + n)$。