合并两个有序数组

大忽悠爱学习

发布于 2022-05-05 19:10:08

1.4K0

自己的写法：对较长的nums1数组使用了双指针法，qp一个在前一个在后，初始时分别指向nums1的第一个元素和第二个元素，分情况讨论有三种，如下代码所示：

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        //双指针
        int q = 0;
        int p = 1;
        for (int i = 0; i < n; i++)
        {
            q = 0;
            p = 1;
             //一共三种情况
                //1.插在数组第一个元素前面
                if (nums2[i] <=nums1[0])
                {
                    for (int j = m-1; j >= 0; j--)
                    {
                        nums1[j + 1] = nums1[j];
                    }
                    nums1[0] = nums2[i];
                    m++;
                    continue;
                }
                //2.插在数组最后一个元素的后一个位置
                if (nums2[i] >= nums1[m - 1])
                {
                    nums1[m] = nums2[i];
                    m++;
                    continue;
                }
                //3.插在快慢指针qp之间
                while (p < m)
                {
                    if (nums2[i] <= nums1[p] && nums2[i] > nums1[q])
                    {
                        for (int j = m - 1; j >= p; j--)
                        {
                            nums1[j + 1] = nums1[j];
                        }
                        nums1[q + 1] = nums2[i];
                        m++;
                        break;
                    }
                    q++, p++;
                }
        }
    }
};
void test()
{
    vector<int> v1 = { 1,2,3,0,0,0 };
    vector<int> v2 = { 2,5,6 };
    Solution s;
    s.merge(v1, 3, v2, 3);
    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1[i] << " ";
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

参照他人的解法

方法一 : 合并后排序

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        //第一步合并两个容器
        int j = 0;
        for (int i = m; i < m + n; i++)
        {
            nums1[i] = nums2[j++];
        }
        //对合并后的容器进行排序
        sort(nums1.begin(), nums1.end());
    }
};

方法三 : 双指针 / 从后往前

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        int i = m + n - 1;
        m--, n--;
        while (n >= 0)
        {
            while (m >= 0 && (nums1[m] > nums2[n]))
            {
                nums1[i--] = nums1[m--];
            }
            nums1[i--] = nums2[n--];
        }
    }
};