LeetCode 88. 合并两个有序数组
题目描述
思路分析
题目要求将两个有序数组合并成一个有序数组，并且结果存储在第一个数组中。我们可以利用双指针从后往前遍历的方法来解决这个问题。具体步骤如下：
- 初始化三个指针：
p1指向nums1的有效部分的最后一个元素。p2指向nums2的最后一个元素。p指向nums1的最后一个位置。- 从后往前遍历
nums1和nums2，比较p1和p2指向的元素，将较大的元素放到p指向的位置，然后移动相应的指针。- 如果
nums2还有剩余元素没有处理完，则将这些元素直接复制到nums1的前面。
时间和空间复杂度
- 时间复杂度：O (m + n)，其中 m 和 n 分别是
nums1和nums2的长度。- 空间复杂度：O (1)，因为我们是原地修改
nums1。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func merge(nums1 []int, m int, nums2 []int, n int) {
p, p1, p2 := m+n-1, m-1, n-1
for p1 >= 0 && p2 >= 0 {
if nums1[p1] > nums2[p2] {
nums1[p] = nums1[p1]
p1--
} else {
nums1[p] = nums2[p2]
p2--
}
p--
}
for p2 >= 0 {
nums1[p] = nums2[p2]
p2--
p--
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
while (p2 >= 0) {
nums1[p] = nums2[p2];
p2--;
p--;
}
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！