面试经典150题（第1题）

准大三生，最近一直在准备寒假实习，想要每天坚持刷Leetcode上面的一些经典面试算法题，选定了掘金作为自己的记录的平台！

面试经典150题
数组/字符串
合并两个有序数组(https://leetcode.cn/studyplan/top-interview-150/)

题目：给你两个按 非递减顺序 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。请你 合并`nums2` 到 `nums1` 中，使合并后的数组同样按 非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。

不用多想，若是单纯考虑最小的时间复杂度以及空间复杂度下完成，一般是采用双指针，题目中刚好要求要让合并后的元素存储进nums1数组中，则此时的空间复杂度相对来说也是极小的，我们可以沿着此思路进行求解：

1、刚开始的思路
对于nums1数组，采用双指针，从左到右依次进行存储，在存储之前进行比较nums1和nums2的元素大小（本质上就是先选择小的元素放置在nums1数组中的左侧）

代码如下：

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

　　问题是将两个数组中每次比较较小的元素往nums1中存储的时候，有可能会产生覆盖的情况，因为若是nums2中元素存储的过快，然后nums1中的指针i记录的比较的数组元素将会被更新的nums1的元素覆盖，造成最终生成的数组会出现多个一样的值!

解决办法：若是想要采用这种办法必须重新定义一个数组，将nums1和nums2中的元素全部存储进去后，最后一个for循环拷贝所有的进入
nums1数组即可！缺点是耗费额外的空间，空间复杂度直接增大一倍！

2.相对来说，较优的思路

想了好久，从评论区看到的解题思路，为了避免使用额外的空间，合理使用nums1数组的空间，这里对于nums1和nums2原始数据采用从右边向左的存储进行，即从大到小

相关代码也是要简单不少：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = m + n - 1,  i = m - 1, j = n - 1;
        //参考题解，从后往前进行
        while(k >= 0){
            if(i >= 0 && j >= 0){
                if(nums1[i] >= nums2[j]){
                    nums1[k] = nums1[i];
                    i--;
                }else{
                    nums1[k] = nums2[j];
                    j--;
                }
            }else if(j >= 0 && i < 0){
                    while(j >= 0){
                        nums1[j] = nums2[j];
                        j--;
                    }
                    break;
            }else{
                break;
            }
            k--;
        }   
    }
};

2023年9月6号