0088. 合并两个有序数组

题目地址(88. 合并两个有序数组)

题目描述

1
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
2
3
说明:
4
5
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
6
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
7
示例:
8
9
输入:
10
nums1 = [1,2,3,0,0,0], m = 3
11
nums2 = [2,5,6], n = 3
12
13
输出: [1,2,2,3,5,6]
Copied!

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • loomberg
  • facebook
  • microsoft

前置知识

  • 归并排序

思路

符合直觉的做法是将nums2插到num1的末尾, 然后排序
具体代码:
1
// 这种解法连m都用不到
2
// 这显然不是出题人的意思
3
if (n === 0) return;
4
let current2 = 0;
5
for (let i = nums1.length - 1; i >= nums1.length - n; i--) {
6
nums1[i] = nums2[current2++];
7
}
8
nums1.sort((a, b) => a - b); // 当然你可以自己写排序,这里懒得写了,因为已经偏离了题目本身
Copied!
这道题目其实和基本排序算法中的merge sort非常像。
我们先来回顾一下 merge sort 的 merge 过程。merge 的过程可以是先比较两个数组的头元素,然后将较小的推到最终的数组中,并将其从原数组中出队列。不断循环直到两个数组都为空。
具体代码如下:
1
// 将nums1 和 nums2 合并
2
function merge(nums1, nums2) {
3
let ret = [];
4
let i = (j = 0);
5
while (i < nums1.length || j < nums2.length) {
6
if (i === nums1.length) {
7
ret.push(nums2[j]);
8
j++;
9
continue;
10
}
11
12
if (j === nums2.length) {
13
ret.push(nums1[i]);
14
i++;
15
continue;
16
}
17
const a = nums1[i];
18
const b = nums2[j];
19
if (a > b) {
20
ret.push(nums2[j]);
21
j++;
22
} else {
23
ret.push(nums1[i]);
24
i++;
25
}
26
}
27
return ret;
28
}
Copied!
但是 merge sort 很多时候,合并的时候我们通常是新建一个数组,但是这道题目要求的是原地修改.这就和 merge sort 的 merge 过程有点不同。这里要求原地修改。如果使用类似上面的方法,如果采用从头开始遍历,需要将 nums1 的前 m 个数组放到另一个数组中避免写指针写入的干扰。 这样空间复杂度就是 $O(m)$。其实我们能只要从后往前比较,并从后往前插入即可。
我们需要三个指针:
  1. 1.
    写指针 current, 用于记录当前填补到那个位置了
  2. 2.
    m 用于记录 nums1 数组处理到哪个元素了
  3. 3.
    n 用于记录 nums2 数组处理到哪个元素了
如图所示:
  • 灰色代表 num2 数组已经处理过的元素
  • 红色代表当前正在进行比较的元素
  • 绿色代表已经就位的元素

关键点解析

  • 从后往前比较,并从后往前插入,这样可避免写指针影响,同时将空间复杂度降低到 $O(1)$

代码

代码支持:Python3, C++, Java, JavaScript
JavaSCript Code:
1
var merge = function (nums1, m, nums2, n) {
2
// 设置一个指针,指针初始化指向nums1的末尾(根据#62,应该是index为 m+n-1 的位置,因为nums1的长度有可能更长)
3
// 然后不断左移指针更新元素
4
let current = m + n - 1;
5
6
while (current >= 0) {
7
// 没必要继续了
8
if (n === 0) return;
9
10
// 为了方便大家理解,这里代码有点赘余
11
if (m < 1) {
12
nums1[current--] = nums2[--n];
13
continue;
14
}
15
16
if (n < 1) {
17
nums1[current--] = nums1[--m];
18
continue;
19
}
20
// 取大的填充 nums1的末尾
21
// 然后更新 m 或者 n
22
if (nums1[m - 1] > nums2[n - 1]) {
23
nums1[current--] = nums1[--m];
24
} else {
25
nums1[current--] = nums2[--n];
26
}
27
}
28
};
Copied!
C++ code:
1
class Solution {
2
public:
3
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
int current = m + n - 1;
5
while (current >= 0) {
6
if (n == 0) return;
7
if (m < 1) {
8
nums1[current--] = nums2[--n];
9
continue;
10
}
11
if (n < 1) {
12
nums1[current--] = nums1[--m];
13
continue;
14
}
15
if (nums1[m - 1] > nums2[n - 1]) nums1[current--] = nums1[--m];
16
else nums1[current--] = nums2[--n];
17
}
18
}
19
};
Copied!
Java Code:
1
class Solution {
2
public void merge(int[] nums1, int m, int[] nums2, int n) {
3
int i=m-1, j=n-1, k=m+n-1;
4
// 合并
5
while(i>=0 && j>=0)
6
{
7
if(nums1[i] > nums2[j])
8
{
9
nums1[k--] = nums1[i--];
10
}
11
else
12
{
13
nums1[k--] = nums2[j--];
14
}
15
}
16
// 合并剩余的nums2
17
while(j>=0)
18
{
19
nums1[k--] = nums2[j--];
20
}
21
}
22
}
Copied!
Python Code:
1
class Solution:
2
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
3
"""
4
Do not return anything, modify nums1 in-place instead.
5
"""
6
pos = m + n - 1
7
while m > 0 and n > 0:
8
if nums1[m - 1] < nums2[n - 1]:
9
nums1[pos] = nums2[n - 1]
10
n -= 1
11
else:
12
nums1[pos] = nums1[m - 1]
13
m -= 1
14
pos -= 1
15
while n > 0:
16
nums1[pos] = nums2[n - 1]
17
n -= 1
18
pos -= 1
Copied!
复杂度分析
  • 时间复杂度:$O(M + N)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。