最近开始找工作，面试遇到不止一次合并有序数组/链表这种题了，这里也记录一下，感觉考察频率还挺高。
题目描述
给你两个有序整数数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。
初始化nums1和nums2的元素数量分别为m和n。你可以假设nums1的空间大小等于m+n，这样它就有足够的空间保存来自nums2的元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
1. 合并后再排序
直接将num2放到num1的剩余空间中，然后对合并后的数组进行排序，这样很简单直观。
1
2
3
4
5
6
7
8
| class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
nums1[m:] = nums2[::]
nums1.sort()
return None
|
但是这样做就没有用到题目中“有序数组”这个条件了，即使第二步调用的是Python标准库中的sort，前面步骤用切片优化，效率也不是很好。
- 时间复杂度: O((m+n)log(m+n))
- 空间复杂度: O(1)
2. 辅助数组 + 双指针
阅读题目里的“有序数组”这个条件，可以先建立一个辅助数组tmp，用两个指针p1和p2分别从头遍历num1与num2，依次对比p1和p2所指向值得大小，按顺序将值放入tmp中；遍历完成后，将tmp的值再copy给nums1即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1 = 0
p2 = 0
p = 0
tmp = [0] * (m + n)
while p1 < m and p2 < n:
if nums1[p1] <= nums2[p2]:
tmp[p] = nums1[p1]
p1 += 1
else:
tmp[p] = nums2[p2]
p2 += 1
p += 1
if p1 == m:
tmp[p1 + p2:] = nums2[p2:]
elif p2 == n:
tmp[p1 + p2:] = nums1[p1:m]
nums1[::] = tmp[::]
return None
|
3. 原地合并 + 双指针（从后向前）
鉴于题目中明确指出“nums1的空间大小等于m+n”，即num1后面的空余空间是足够容纳num2的n个元素的，利用这个条件，可以不申请辅助数组，从两个数组的有效位尾部开始向前遍历，直接将两者对比的结果放到空余空间中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p = m + n - 1
while m and n:
if nums1[m-1] >= nums2[n-1]:
nums1[p] = nums1[m-1]
m -= 1
else:
nums1[p] = nums2[n-1]
n -= 1
p -= 1
nums1[:n] = nums2[:n]
return None
|
这样就避免了辅助空间的申请，可以适当降低一点空间复杂度。
顺便练习一下Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| impl Solution {
pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
let mut i = (m - 1) as usize;
let mut j = (n - 1) as usize;
let mut p = i + j + 1;
while i < (m as usize) && j < (n as usize) {
if nums1[i] >= nums2[j] {
nums1[p] = nums1[i];
i -= 1;
} else {
nums1[p] = nums2[j];
j -= 1;
}
p -= 1;
}
if j >= 0 {
nums1[..j+1].copy_from_slice(&nums2[0..j+1]);
}
}
}
|