【4.5】LeetCode每日一题· 合并两个有序数组

2021年04月05日 20时14分

标签： LeetCode 数组

## 题目描述
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

#### 示例1
```
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
```

#### 示例2
```
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/merge-sorted-array "题目链接")

## 解题思路
1.将` nums2`数组元素全都放在`nums1`之后，然后排序。时间复杂度$$O((m+n) \log(m+n))$$

2.参考有序链表的合并方法，新建一个数组`sorted`，并设指针`i`，`j`分别指向`num1`和` num2`的开头，然后比较`nums1[i]`和`nums2[j]`的大小，将其中较大的一个放在`sorted`数组最后，并将对应的指针后移一位，直到某一个指针到达了数组尾部。然后将指针未到达尾部的另一个数组中的剩余元素全部按顺序放到`sorted`数组最后；最后将`sorted`数组拷贝到`nums1`中。时间复杂度$$O(m+n)$$，空间复杂度$$O(m+n)$$；

3.如何在不利用额外内存的情况下完成该任务？考虑到`nums1`数组后面给我们留了填数字的空位，我们可以仿照方法2，但是此时需要对两个数组进行**倒序比较**，也就是将指针初始设置为指向`nums1`和`nums2`的最后一个有效的数字，然后取其中较大的数字放在`nums1`数组的最后，直到某一个指针指向数组开头为止，然后将另一个数组中剩余的数字全部倒序放在`nums1`中，这样就可以在$$O(1)$$空间复杂度内完成任务。

### 代码
```cpp
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1, j = n-1, pos = nums1.size()-1;
        while(i >= 0 && j >= 0){
            if(nums1[i] > nums2[j]){
                nums1[pos--] = nums1[i--];
            }else{
                nums1[pos--] = nums2[j--];
            }
        }
        while(i >= 0) nums1[pos--] = nums1[i--];
        while(j >= 0) nums1[pos--] = nums2[j--];
    }
};
```

## 用时和内存
> 执行用时：4 ms，在所有 C++提交中击败了63.89%的用户
> 内存消耗：8.7 MB，在所有 C++提交中击败了93.93%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.5】LeetCode每日一题· 合并两个有序数组

所有评论

暂无评论

新增评论