题目描述（简单难度）

给两个有序数组，把第二个数组合并到第一个数组中，保持有序。可以注意到第一个数组已经为我们多开辟了第二个数组所需要的空间。

解法一直接法

简单粗暴，nums1 作为被插入的数组，然后遍历 nums2。用两个指针 i 和 j ，i 指向 nums1 当前判断的数字，j 指向 num2 当前遍历的数字。如果 j 指向的数字小于 i 指向的数字，那么就做插入操作。否则的话后移 i ，找到需要插入的位置。

时间复杂度：极端情况下，如果每次都需要插入，那么是 O（n²）。

空间复杂度：O（1）。

两个有序数组的合并，其实就是归并排序中的一个步骤。回想下，我们当时怎么做的。

我们当时是新开辟一个和 nums1 + nums2 等大的空间，然后用两个指针遍历 nums1 和 nums2，依次选择小的把它放到新的数组中。

时间复杂度： O（n）。

空间复杂度：O（1）。

可以注意到，我们只考虑如果 nums1 遍历结束，将 nums2 直接加入。为什么不考虑如果 nums2 遍历结束，将 nums1 直接加入呢？因为我们最开始的时候已经把 nums1 全部放到了末尾，所以不需要再赋值了。

本以为自己的解法二已经很机智了，直到看到了，发现了一个神仙操作。

解法二中我们的思路是，把 nums1 当作合并后的大数组，依次从两个序列中选较小的数，此外，为了防止 nums1 原有的数字被覆盖，首先先把他放到了末尾。

那么，我们为什么不从 nums1 的末尾开始，依次选两个序列末尾较大的数插入呢？同样是 3 个指针，只不过变成哪个数大就对应的添加哪个数。

空间复杂度：O（1）。

这道题看起来简单，但用到的思想很经典了。解法二中充分利用已有空间的思想，以及解法三中逆转我们的惯性思维，给定的数组从小到大，然后惯性上习惯从小到大，但如果逆转过来，从大的选，简直是神仙操作了！

添加好友一起进步~

如果觉得有帮助的话，可以点击这里给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击查看详情