88. 合并两个有序数组
双指针
思路
分别设置一个头部指针，然后依次比较大小，用一个临时数组存放较小值。肯定会有一个数组未被检测完，因为是有序的，所以依次插入即可。这里我联想到了归并算法，都有一个余数检测机制。
代码实现
class Solution { public: void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { if (!nums2.size()) { return; } vector<int> temp; int p1 = 0, p2 = 0; while (p1 < m && p2 < n) { if (nums1[p1] > nums2[p2]) { temp.push_back(nums2[p2]); p2++; } else { temp.push_back(nums1[p1]); p1++; } } while (p1 < m) { temp.push_back(nums1[p1++]); } while (p2 < n) { temp.push_back(nums2[p2++]); } int i = 0; while (i < m + n) { nums1[i] = temp[i]; i++; } } };
复杂度分析
时间复杂度：O ( m + n )
指针移动单调递增，最多移动 m + n 次，再加上最后整个 t e m p 数组复制需要 m + n 次，一共 2 ( m + n )
空间复杂度：O ( m + n )
需要建立长度为 m+n 的中间数组
逆向双指针
思路
因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。 因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。
这里需要注意，如果 nums1 的数字已经复制完，不要忘记把 nums2 的数字继续复制；如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要改变，因为它们已经被排好序。
代码实现
class Solution { public: void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { // 后续m和n作为下标使用，所以要自减 int pos = m-- + n-- - 1; while (m >= 0 && n >= 0) { nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]; } while (n >= 0) { nums1[pos--] = nums2[n--]; } } };
复杂度分析
时间复杂度：O ( m + n )
空间复杂度：O ( 1 )
