合并两个有序数组
# 📃 题目描述
题目链接:88. 合并两个有序数组 (opens new window)
# 🔔 解题思路
# 双指针
需要新开一个数组
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums2 == null || nums2.length == 0) {
return ;
}
int[] nums3 = new int[m + n];
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (p1 < m && p2 < n) {
if (nums1[p1] < nums2[p2]) {
nums3[p3 ++] = nums1[p1 ++];
}
else {
nums3[p3 ++] = nums2[p2 ++];
}
}
while (p1 < m) {
nums3[p3 ++] = nums1[p1 ++];
}
while (p2 < n) {
nums3[p3 ++] = nums2[p2 ++];
}
for (int i = 0; i < nums1.length; i ++) {
nums1[i] = nums3[i];
}
}
}
# 逆向双指针
nums1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进 nums1 的最后面
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums2 == null || nums2.length == 0) {
return ;
}
// 从后往前遍历
int p1 = m - 1;
int p2 = n - 1;
int tail = nums1.length - 1;
while (p2 >= 0) {
// p1 < 0 (p1 遍历完了但 p2 还没遍历完,直接把 p2 的剩余元素依次放到 nums1 的剩余空间就行了
if (p1 < 0 || nums2[p2] >= nums1[p1]) {
nums1[tail --] = nums2[p2 --];
}
else {
nums1[tail --] = nums1[p1 --];
}
}
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10