88. 合并两个有序数组(Easy)

题目描述

给定两个有序数组，把两个数组合并为一个。

样例

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 
Output: nums1 = [1,2,2,3,5,6]
# 要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

题解

由于要求原地归并，所以应该从nums1的数组末端开始，逐个比较数字的大小

Python 示例

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.
        """
        pos = m + n - 1
        m, n = m - 1, n - 1
        while  m >= 0 and n >= 0:
            if nums1[m] > nums2[n]:
                nums1[pos] = nums1[m]
                m -= 1
            else:
                nums1[pos] = nums2[n]
                n -= 1
            pos -= 1
        if n >= 0:
            nums1[:n + 1] = nums2[:n + 1] 

C++示例

C++ 有些小技巧，所以写起来比较简洁

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

Go 示例

func merge(nums1 []int, m int, nums2 []int, n int)  {
    pos := m + n - 1
    m, n = m - 1, n - 1
    for m >= 0 && n >= 0 {
        if nums1[m] > nums2[n] {
            nums1[pos] = nums1[m]
            pos -= 1
            m -= 1
        } else {
            nums1[pos] = nums2[n]
            pos -= 1
            n -= 1
        }
    }
    for n >= 0 {
        nums1[pos] = nums2[n]
        pos--
        n--
    }
}