LeetCode每日一题:合并两个有序数组

链接: 合并两个有序数组

---

这题有个要求：能不能使用O(m+n)的时间复杂度完成？

那当然是有的！

思路：用两个指针分别指向两个数组的尾部！这个很关键！
然后从后向前遍历。又题目可知，nums1的大小肯定是m+n的，且nums1的后半部分是空的，直接覆盖是没影响的。
所以就是将nums2中的元素与nums1中的比较，谁大就先放谁进去。

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