leetcode打卡-0088合并两个有序数组

最近开始找工作，面试遇到不止一次合并有序数组/链表这种题了，这里也记录一下，感觉考察频率还挺高。

题目描述

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1. 合并后再排序

直接将num2放到num1的剩余空间中，然后对合并后的数组进行排序，这样很简单直观。

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[m:] = nums2[::]
        nums1.sort()
        return None

但是这样做就没有用到题目中“有序数组”这个条件了，即使第二步调用的是Python标准库中的sort，前面步骤用切片优化，效率也不是很好。

• 时间复杂度: O((m+n)log(m+n))
• 空间复杂度: O(1)

2. 辅助数组 + 双指针

阅读题目里的“有序数组”这个条件，可以先建立一个辅助数组tmp，用两个指针p1和p2分别从头遍历num1与num2，依次对比p1和p2所指向值得大小，按顺序将值放入tmp中；遍历完成后，将tmp的值再copy给nums1即可。

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 = 0
        p2 = 0
        p = 0
        tmp = [0] * (m + n)

        while p1 < m and p2 < n:
            if nums1[p1] <= nums2[p2]:
                tmp[p] = nums1[p1]
                p1 += 1
            else:
                tmp[p] = nums2[p2]
                p2 += 1
            p += 1
        
        if p1 == m:
            tmp[p1 + p2:] = nums2[p2:]
        elif p2 == n:
            tmp[p1 + p2:] = nums1[p1:m]

        nums1[::] = tmp[::]

        return None

• 时间复杂度O(m+n)
• 空间复杂度O(m+n)

3. 原地合并 + 双指针（从后向前）

鉴于题目中明确指出“nums1的空间大小等于m+n”，即num1后面的空余空间是足够容纳num2的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.
        """
        p = m + n - 1

        while m and n:
            if nums1[m-1] >= nums2[n-1]:
                nums1[p] = nums1[m-1]
                m -= 1
            else:
                nums1[p] = nums2[n-1]
                n -= 1
            p -= 1
        

        nums1[:n] = nums2[:n]

        return None

这样就避免了辅助空间的申请，可以适当降低一点空间复杂度。

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

顺便练习一下Rust

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let mut i = (m - 1) as usize;
        let mut j = (n - 1) as usize;
        let mut p = i + j + 1;

        while i < (m as usize) && j < (n as usize) {
            if nums1[i] >= nums2[j] {
                nums1[p] = nums1[i];
                i -= 1;
            } else {
                nums1[p] = nums2[j];
                j -= 1;
            }
            p -= 1;
        }

        if j >= 0 {
            nums1[..j+1].copy_from_slice(&nums2[0..j+1]);
        }
    }
}