昨天腾讯一面上来就给我整的这道 easy 难度的题，然后我太紧张了还想了一会儿，差点炸裂。
题目链接
LeetCode 88. 合并两个有序数组[1]
题目描述
给你两个有序整数数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。
说明：
初始化nums1和nums2的元素数量分别为m和n。你可以假设nums1有足够的空间（空间大小大于或等于m + n）来保存nums2中的元素。
示例1
输入：nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出:[1,2,2,3,5,6]解释：
题解
看到这道题，脑海里应该第一时间想到的是归并排序，但是归并排序需要一个额外的数组用来保存排序后的数组，这里不允许使用额外空间。
那么我们还是用归并排序的思路来做，试一下两个指针i = 0和j = 0，初始的时候分别指着nums1[0]和nums2[0]。然后比较nums1[i]和nums2[j]大小，如果nums1[i]更小，那么就放在原位不动它，然后i += 1。如果nums2[j]更小，那么就交换nums1[i]和nums2[j]，然后还是i += 1。这么看貌似可行哦？但是最终一定会先遍历完nums1，然后j还是停留在0，然后你会发现nums2中的数字还是乱序的，根本没法处理。
那么怎么利用上nums1后面多出的那么多空位呢？我们可以换个思路，从最大的开始遍历。两个指针初始的时候i = m-1和j = n-1，然后将较大值填充到nums1的最后面。最后如果nums2中还有剩余，就依次填充到nums1最前面就行了。
这样为什么就可以了呢？因为如果从小到大遍历的话，元素会覆盖掉nums1中还没遍历的元素。但是从大到小是填充到尾部，就不会产生覆盖。就算极限情况下nums2中元素全部大于nums1中元素，也不会覆盖到nums1的最后一个元素。
面试官最后还会问你有啥优化，我当时图省事，最后还把nums1中剩下元素填充到nums1最前面了，其实完全没有必要，本来就是有序的，等于没有做事。
代码
c++
class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = m-1, j = n-1, k = m+n-1;while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) nums1[k--] = nums1[i--];else nums1[k--] = nums2[j--];}while (j >= 0) nums1[k--] = nums2[j--];}};
python
class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:i, j = m-1, n-1while i >= 0 and j >= 0:if nums1[i] > nums2[j]:nums1[i+j+1] = nums1[i]i -= 1else:nums1[i+j+1] = nums2[j]j -= 1while j >= 0:nums1[j] = nums2[j]j -= 1
参考资料
[1]
LeetCode 88. 合并两个有序数组:https://leetcode-/problems/merge-sorted-array/
