精选50题之 88. 合并两个有序数组

谁践踏了优雅 2024-04-19 10:36 62阅读 0赞

### 腾讯精选练习（50 题）之 88. 合并两个有序数组 ###

*   *  原题目链接
     *  直接实现
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  写在最后

## [原题目链接][Link 1] ##

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。  
说明:  
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。  
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

> 输入:  
> nums1 = \[1,2,3,0,0,0\], m = 3  
> nums2 = \[2,5,6\], n = 3  
> 输出: \[1,2,2,3,5,6\]

## 直接实现 ##

真-暴力实现 合并后再排序怎么了?

class Solution {
        
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
            int j = m;
            for(int i = 0; i < n; i++)
            {
        
                nums1[j++] = nums2[i];
            }
            sort(nums1.begin(), nums1.end());
        }
    };

![在这里插入图片描述][2019091723551066.png]  
复杂度分析：

*  时间复杂度：O((m+n)log(m+n))
 *  空间复杂度：O(1)

暴力法结果很不错 都不想再往下分析了?

## 题目分析 ##

可否在将两个数字合并前先排序呢？当然可以。  
和之前 [精选50题之 15. 三数之和][50_ 15.] 中使用过的双指针的思路相近

## 解题分析 ##

指针p1 置为 nums1的复制数组的开头， p2为 nums2的开头，在每一步将此时最小值放入输出到数组nums\[p++\]中

## 代码实现 ##

class Solution {
        
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
            vector<int> nums11 = nums1;
            int p1 = 0, p2 = 0, p = 0;
            while (p1 < m && p2 < n)
                nums1[p++] = nums11[p1] < nums2[p2] ? nums11[p1++] : nums2[p2++];
            if(p1 < m)
            {
        
                while (p1 < m)
                    nums1[p++] = nums11[p1++];     
            }
            else
            {
        
                while (p2 < n)
                    nums1[p++] = nums2[p2++];     
            }
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析：

*  时间复杂度：O(m+n)
 *  空间复杂度：O(m) nums1的复制数组nums11所占用空间

## 其他方式 ##

Q：时间复杂度降低至O(log(m+n))不太现实，但是空间复杂度可以降低么？可以不引入复制数组么？  
A：可以。

Q：只要是正向查找，必然涉及额外空间……  
A：为什么不试试 **反向查找** 呢？

豁然开朗……

class Solution {
        
    public:
        void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
            vector<int> nums11 = nums1;
            int p1 = m - 1, p2 = n - 1, p = m + n - 1;
            while (p1 >= 0 && p2 >= 0)
                nums1[p--] = nums11[p1] > nums2[p2] ? nums11[p1--] : nums2[p2--];
            // 不需要重复讨论p1>0的情况
            while (p2 >= 0)
                    nums1[p--] = nums2[p2--];   
        }
    };

![在这里插入图片描述][2019091800503722.png]  
复杂度分析：

*  时间复杂度：O(m+n)
 *  空间复杂度：O(1)

## 写在最后 ##

逆向思维？！

[Link 1]: https://leetcode-cn.com/problems/merge-sorted-array/
[2019091723551066.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/001df69283cd4124bb57d06d61ed31ce.png
[50_ 15.]: https://blog.csdn.net/weixin_41728431/article/details/100187983
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f2af65cb7d5f4440a7cd372cd8817a1a.png
[2019091800503722.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0e813d39eb2d452f9e2fc3e2860fc3ef.png