LeetCode 88. 合并两个有序数组
题目描述
思路分析
双指针问题
参考代码
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
21
22
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
// 从后往前合并两个数组
for i >= 0 && j >= 0 {
if nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
// 如果 nums2 还有剩余元素，复制到 nums1
for j >= 0 {
nums1[k] = nums2[j]
j--
k--
}
}
- 时间复杂度：O(m + n)
- 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p = m + n - 1, p1 = m - 1, p2 = n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--];
} else {
nums1[p--] = nums2[p2--];
}
}
while (p2 >= 0) {
nums1[p--] = nums2[p2--];
}
}
}
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！