合并两个有序数组

        给定两个按非递减顺序排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。需要将 nums2 合并到 nums1 中，使合并后的数组同样按非递减顺序排列。注意：合并后的数组应存储在 nums1 中，且 nums1 的初始长度为 m + n，前 m 个元素为有效元素，后 n 个元素为占位的 0。

解决思路:

        由于 nums1 的长度足够容纳合并后的数组，可以从后向前填充 nums1，避免覆盖 nums1 中的元素。具体步骤如下：

双指针法（从后向前遍历）

        该方法适用于两个已排序数组的合并，且第一个数组有足够空间容纳合并后的结果。通过从后向前遍历，避免数据覆盖问题。

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–];
}
}

直接合并后排序

        将第二个数组直接拼接到第一个数组的尾部，然后对整个数组进行排序。虽然简单，但时间复杂度较高（O((m+n)log(m+n))），适用于小规模数据。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = 0; i < n; ++i) {
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}

注意事项:

        1.确保第一个数组的空间足够容纳合并后的所有元素。

        2.双指针法的时间复杂度为 O(m+n)，是更高效的解决方案。

        3.若从前往后遍历，需要额外空间存储中间结果，效率较低。