力扣日记88-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣日记88。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目

LeetCode 88. 合并两个有序数组

1.1 题意

将两个有序数组合并

1.2 分析

第一直接想到归并排序，但是本题有些特殊

合并后数组存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

这个题目一下子激发的思路是原地算法，空间复杂度O(1)。
想到nums1后边的位置没有使用，便大胆想直接从后面的大数开始归并。

这时担心会不会归并过程中直接把nums1中的有效数字直接覆盖？设想一个最坏情况，nums2一直往nums1放（即nums2大于nums1中所有数），放完刚好不会覆盖掉nums1中的有效区域。
事实上nums1中的空闲区域长度一直是nums2中未放置的数的个数。

1.3 我的解法

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // choose big digit first
        // 从后往前选大数
        int ptr1 = m-1, ptr2 = n-1;
        int prtAns = m+n-1;
        // traversal in reverse order
        while(prtAns>=0){
            if(ptr1<0){
                // nums1已经全部放完，只需要放nums2
                // finish nums1
                // copy nums2
                nums1[prtAns--] = nums2[ptr2--];
            }
            else if(ptr2<0){
                // nums2已经全部放完，只需要放nums1
                // 事实上这步可以直接下标--
                // 因为此时ptrAns 已经等于 ptr1
                // finish nums2
                // copy nums1
                nums1[prtAns--] = nums1[ptr1--];
            }
            else{
                // 从两个数组中选大数放再指定位置
                if(nums1[ptr1] >= nums2[ptr2]){
                    nums1[prtAns--] = nums1[ptr1--];
                }
                else{
                    nums1[prtAns--] = nums2[ptr2--];
                }
            }
        }
    }
};