精选力扣500题第22题 LeetCode 88. 合并两个有序数组【c++详细题解】

客官°小女子只卖身不卖艺 2021-07-24 15:52 404阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路1
         *  3、代码1
         *  4、思路2
         *  5、代码2

### 1、题目 ###

给你两个有序整数数组 `nums1` 和 `nums2`，请你将 `nums2` 合并到 `nums1`中，使 `nums1` 成为一个有序数组。

初始化 `nums1` 和 `nums2`的元素数量分别为 `m` 和`n`。你可以假设 `nums1` 的空间大小等于 `m + n`，这样它就有足够的空间保存来自 `nums2`的元素。

**示例 1：**

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

**示例 2：**

输入：nums1 = [1], m = 1, nums2 = [], n = 0
    输出：[1]

**提示：**

*  `nums1.length == m + n`
 *  `nums2.length == n`
 *  `0 <= m, n <= 200`
 *  `1 <= m + n <= 200`
 *  `-109 <= nums1[i], nums2[i] <= 109`

### 2、思路1 ###

**(二路归并）** O ( n ) O(n) O(n)

*  1、新开一个数组`ans`用来存贮合并后的有序元素
 *  2、定义两个指针`i`，和`j`分别指向`nums1`和`nums2`，每次将两个指针所指向的较小的数添加到`ans`中
 *  3、将`ans`数组赋值给`num1`

**时间复杂度**： O ( n ) O(n) O(n)

**空间复杂度为**: 由于新开了一个数组`ans`,因此空间复杂度为 O ( n ) O(n) O(n)。

### 3、代码1 ###

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

### 4、思路2 ###

在上面**二路归并**算法中，需要临时一个构建一个数组，空间复杂度不是常数，通过观察题，没有充分利用题目所给的条件，`nums1`已经开够了足够大，如果直接在`nums1`上合并，便不需要额外的空间，而如果从前往后合并，则会覆盖元素得到错误结果，再通过观察，如果从后往前合并的方式，则不会覆盖，是理想的解法，时间 O ( n ) O(n) O(n)，空间常数。

**步骤如下**

*  1、初始化`k = m + n - 1`
 *  2、定义两个指针`i`，和`j`分别指向`nums1`和`nums2`，每次将两个指针所指向的较大的数放在`k`的位置，同时`i`或者`j` 和 `k`同时减`1`
 *  3、如果`while(j >= 0)`再将`nums2`中剩余的数放入`nums1`中

### 5、代码2 ###

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

**原题链接：**[88. 合并两个有序数组][88.]

**题目**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[88.]: https://leetcode-cn.com/problems/merge-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/999d897cdcda4abc90377f5997b26bbf.png