【算法题解】6.合并两个有序数组

墨蓝 2024-03-30 12:36 82阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一：双指针
     *   *  解题思路
         *  图解
         *  代码实现
         *  复杂度分析
     *  解法二：逆向双指针
     *   *  解题思路
         *  图解
         *  代码实现
         *  复杂度分析

### 题目 ###

给你两个按 非递减顺序 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。

请你 合并 `nums2` 到 `nums1` 中，使合并后的数组同样按 非递减顺序 排列。

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

### 解法一：双指针 ###

#### 解题思路 ####

因为 `nums1` 和 `nums2` 已经是排好序的，所以我们可以使用双指针，`index1` 指向 `nums1`，`index2` 指向 `nums2`，每次选`nums1[index1]` 和 `nums2[index2]` 中的较小值放入答案 `ans[cur++]`，然后将用掉的那个数组的指针往后移动一位。

#### 图解 ####

以 `nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3` 为例，输出：`[1,2,2,3,5,6]`。

![6.合并两个有序数组][6.]

#### 代码实现 ####

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int[] ans = new int[m + n];
            int cur = 0;
            int index1 = 0;
            int index2 = 0;
            while(index1 < m || index2 < n){
        
                if(index2 >= n || index1 < m && nums1[index1] <= nums2[index2]){
        
                    ans[cur++] = nums1[index1++];
                }else{
        
                    ans[cur++] = nums2[index2++];
                }
            }
            for(int i = 0; i < m + n; i++){
        
                nums1[i] = ans[i];
            }
        }
    }

#### 复杂度分析 ####

**时间复杂度**  O ( m + n ) O(m + n) O(m\+n): while循环共执行 m + n 次，for循环同样执行m + n次，总结 2(m + n)次。  
**空间复杂度**  O ( m + n ) O(m + n) O(m\+n): ans 数组长度为 m + n, 其他为常数。

### 解法二：逆向双指针 ###

#### 解题思路 ####

因为 `nums1` 给定的长度是 `m + n`，已经满足合并后的长度，所以我们可以直接用它来存储最终的答案，但是前序双指针在不使用额外的存储空间时无法满足时间复杂度为 O ( m + n ) O(m + n) O(m\+n)。又因为`nums1`的后`n`个位置都是空置的，可以随意修改，所以我们可以考虑逆序双指针的方式，逆序取最大值并逆序放入`nums1`。当逆序第 `k` 个位置计算完成后，`nums1` 逆序的第 `k + 1` 个位置要么刚好是正确答案无需修改，要么已经赋值给已经计算过的位置也可以直接修改。

#### 图解 ####

同样以 `nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3` 为例，输出：`[1,2,2,3,5,6]`。

![在合并两个有序数组][c223ed5fcf054208bed8218f4cf39f4c.png_pic_center]

#### 代码实现 ####

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int index1 = m - 1;
            int index2 = n - 1;
            int cur = m + n -1;
            while(index1 >= 0 || index2 >= 0){
        
                if(index2 < 0 || index1 >= 0 && nums1[index1] >= nums2[index2]){
        
                    nums1[cur--] = nums1[index1--];
                }else{
        
                    nums1[cur--] = nums2[index2--];
                }
            }
        }
    }

#### 复杂度分析 ####

**时间复杂度**  O ( m + n ) O(m + n) O(m\+n): while循环共执行 m + n 次。  
**空间复杂度**  O ( 1 ) O(1) O(1): 常数空间复杂的。

[leetcode]: https://leetcode.cn/problems/merge-sorted-array/description/
[6.]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4fc7302928bb46c7874e7163fb659ba7.png
[c223ed5fcf054208bed8218f4cf39f4c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/be274000c659493cb67f6a13add45702.png