合并兩個有序數(shù)組

題目來源：https://leetcode-cn.com/problems/merge-sorted-array/

題目

給定兩個有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數(shù)組。

說明:

初始化 nums1 和 nums2 的元素數(shù)量分別為 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]

解題思路

1. 采用雙指針的方法，從后面往前遍歷
2. 定義 p1 指針指向 num1 數(shù)字末尾，p2 指向 num2 數(shù)字末尾，p 指向 num1 的最末尾；
3. 從后往前循環(huán)遍歷比較兩個數(shù)組之間元素的大??；
4. 當 p < 0 時，也就是 p1 和 p2 其中一個小于 0，遍歷結(jié)束；
5. 若是 num2 數(shù)組有剩余部分，因為數(shù)組都是有序的，直接將 num2 數(shù)組剩余部分放到 num1 數(shù)組對應的位置。

代碼實現(xiàn)

class Solution:
    def merge(self, nums1, m: int, nums2, n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        
        合并兩個有序數(shù)組為一個有序數(shù)組

        Args:
            num1: 有序數(shù)組 1
            m: num1 的元素數(shù)量
            num2: 有序數(shù)組 2
            n：num2 的元素數(shù)量
        
        Returns:
            返回合并后的有序數(shù)組
        """
        # 通過雙指針的方法，從后向前遍歷的方法、
        # 定義指針 p1 指向 num1 的數(shù)字末尾
        # 定義指針 p2 指向 num2 的數(shù)字末尾
        # 定義指針 p 指向 num1 的最末尾
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1
        # 當 p 小于 0，即是 p1 和 p2 其中一個小于 0，遍歷結(jié)束
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] = nums1[p1]
                p1 -= 1
            p -= 1
        # 兩個數(shù)組都是有序的
        # 若是 p1 先小于 0，將 num2 剩余部分放在 num1 數(shù)組前面
        nums1[:p2 + 1] = nums2[:p2 + 1]

實現(xiàn)效果

merge_result.jpg

以上就是本篇的主要內(nèi)容

歡迎關注微信公眾號《書所集錄》