题解 | #合并两个有序的数组#

class Solution {
public:
    // 经典双指针
    // 但这个和之前面试遇到的最简单的合并还不太一样
    void merge(int A[], int m, int B[], int n) {
        
        // 先写个需要额外开辟数组空间的  O(n) O(n)
        vector<int> ans(m+n);
        int pt1 = 0, pt2 = 0;
        int cur = 0;
        while(pt1<m && pt2<n)
        {
            if(A[pt1]<B[pt2])
            {
                ans[cur] = A[pt1];
                pt1++;
            }
            else
            {
                ans[cur] = B[pt2];
                pt2++;
            }
            cur++;
        }

        
        while(pt1<m)
        {
            ans[cur] = A[pt1];
            pt1++;
            cur++;
        }

        while(pt2<n)
        {
            ans[cur] = B[pt2];
            pt2++;
            cur++;
        }

        //再把 ans赋给 A
        for(int i=0; i<m+n; ++i)
        {
            A[i] = ans[i];
        }
        
        
    }
};

额外开辟空间了 感觉还可以优化