AI毛毛的blog

leetcode打卡-0088合并两个有序数组

最近开始找工作,面试遇到不止一次合并有序数组/链表这种题了,这里也记录一下,感觉考察频率还挺高。

题目描述

给你两个有序整数数组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)

88_01.png

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
  • 时间复杂度O(m+n)
  • 空间复杂度O(m+n)

88_02.png

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

这样就避免了辅助空间的申请,可以适当降低一点空间复杂度。

  • 时间复杂度O(m+n)
  • 空间复杂度O(1)

88_03.png

顺便练习一下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]);
}
}
}