88. 合并两个有序数组
查看题目简单
数组
高频
解法一：reverse-double-pointer
时间复杂度：O(m+n) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 输入数组值和有效元素数量，然后点击开始
代码实现
import java.util.Arrays;
class Solution {
// 逆向双指针，时间复杂度：O(m+n) 空间复杂度：O(1)
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
// 合并后排序。时间复杂度：O((m+n)log(m+n)) 空间复杂度：O(log(m+n))
public void merge1(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
}时间复杂度：O(m+n)
空间复杂度：O(1)
算法思路：
使用逆向双指针合并两个有序数组，避免额外空间开销。
核心思想：
1. 初始化两个指针p1和p2，分别指向nums1和nums2的末尾有效元素
2. 初始化tail指针指向nums1的末尾（包括预留空间）
3. 从后往前遍历，比较nums1[p1]和nums2[p2]的大小
4. 将较大的元素放入nums1[tail]，并移动相应的指针
5. 重复步骤3-4，直到所有元素都被处理
复杂度分析：
- 时间复杂度：O(m+n)，只需遍历两个数组一次
- 空间复杂度：O(1)，只使用了常量级别的额外空间