【leetcode】精选 88. 合并两个有序数组

布满荆棘的人生 2022-08-31 01:49 4阅读 0赞

### 精选 88. 合并两个有序数组 ###

*  题目难度：简单
 *  方法一：逆向双指针

> 链接：[https://leetcode-cn.com/problems/merge-sorted-array/][https_leetcode-cn.com_problems_merge-sorted-array]  
> 来源：力扣（LeetCode）

# 题目难度：简单 #

给你两个有序整数数组 `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

模板

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    
        }
    }

class Solution:
        def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """

# 方法一：逆向双指针 #

整体思路：

从后向前数组遍历

*  因为 `nums1` 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去
 *  设置指针 `p1` 和 `p2` 分别指向 `nums1` 和 `nums2` 的有数字尾部，从尾部值开始比较遍历，同时设置指针 `cur` 指向 `nums1` 的最末尾，每次遍历比较值大小之后，则进行填充
 *  当 `p2<0` 时循环结束，因为是将`nums2`的数据合并到`nums1`里，只要`p2<0`说明`nums2`数组遍历完毕，`nums2`的全部数据都到`nums1`了，无需管`p1`
 *  时间复杂度：`O(m+n)`

确定了主要的思路之后，实现起来其实很简单。

当 `p2 > 0` 时，从后向前比较`num1[p1]` 和 `nums2[p2]` ：

*  如果是 `nums1[p1]` 大，则把`nums1[p1]`放到 `num1` 的第 `cur` 位置，并让 `p1 -= 1 和 cur -= 1` 向前移一位。
 *  如果是 `nums2[p2]` 大，则把 `nums2[p2]` 放到`num1` 的第 `cur` 位置，并让 `p2 -= 1 和 cur -= 1` 向前移一位。

当上面的遍历条件结束的时候，此时 `p1` 和 `p2` 至少有一个小于 0。

*  当 `p1 < 0` 时，说明 `num1` 的数字恰好用完了，此时 `nums2` 可能还剩元素，需要复制到 `nums1` 的头部；
 *  当 `p2 < 0` 时，说明 `num2` 的数字恰好用完了，此时 `nums1` 可能还剩元素，由于剩余的这些元素一定是 `nums1` 和 `nums2` 中最小的元素，所以不用动，直接留在原地就行。

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int p1 = m - 1;  //指向nums1有数据的尾部
            int p2 = n - 1;  //指向nums2有数据的尾部
            int cur = nums1.length - 1; //指向nums1数组的尾部
    
            while(p2 >= 0){
        
                if(p1 >= 0 && nums1[p1] > nums2[p2]){
        
                    nums1[cur--] = nums1[p1--];
                } else {
         // p1 < 0 || nums1[p1] <= nums2[p2]
                	// 都是将nums2的数据拷贝到nums1剩余位置后面
                    nums1[cur--] = nums2[p2--];
                }
            }
        }
    }

class Solution:
        def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
            """
            Do not return anything, modify nums1 in-place instead.
            """
            p1, p2, cur = m - 1, n - 1, len(nums1) - 1
            while p2 >= 0:
                if p1 >= 0 and nums1[p1] > nums2[p2]:
                    nums1[cur] = nums1[p1]
                    p1 -= 1
                    cur -= 1
                else:
                    nums1[cur] = nums2[p2]
                    p2 -= 1
                    cur -= 1

[https_leetcode-cn.com_problems_merge-sorted-array]: https://leetcode-cn.com/problems/merge-sorted-array/