【LetMeFly】88.合并兩個(gè)有序數(shù)組：O(m + 1) + O(1)的做法

力扣題目鏈接：https://leetcode.cn/problems/merge-sorted-array/

給你兩個(gè)按 非遞減順序 排列的整數(shù)數(shù)組?nums1 和 nums2，另有兩個(gè)整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素?cái)?shù)目。

請(qǐng)你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲(chǔ)在數(shù)組 nums1 中。為了應(yīng)對(duì)這種情況，nums1 的初始長(zhǎng)度為 m + n，其中前 m 個(gè)元素表示應(yīng)合并的元素，后 n 個(gè)元素為 0 ，應(yīng)忽略。nums2 的長(zhǎng)度為 n 。

?

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。

示例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。

示例 3：

輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意，因?yàn)?m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。

?

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

?

進(jìn)階：你可以設(shè)計(jì)實(shí)現(xiàn)一個(gè)時(shí)間復(fù)雜度為 O(m + n) 的算法解決此問題嗎？

方法一：三指針（雙指針）

這道題不返回任何值，很顯然，出題者想讓你在nums1數(shù)組上原地修改。

怎么原地修改呢？nums1后面全是$0$，而這些地方本來應(yīng)該是“大數(shù)”，所以我們使用兩個(gè)指針，從$nums1$和$nums2$的大數(shù)區(qū)域往前指，每次將二者較大的那個(gè)放到nums1后面不就可以了嗎。

      tail
      ↓
1 3 0 0
  ↑
2 6
  ↑

$3<6$，所以將$6$放到tail處，

    tail
    ↓
1 3 0 6
  ↑
2 -
↑

$3>2$，所以將$3$放到tail處，

  tail
  ↓
1 - 3 6
↑
2 -
↑

$1<2$，所以將$2$放到tail處，

tail
↓
1 2 3 6
↑
- -

$nums2$的指針指完了，任務(wù)完成，得到$[1,2,3,6]$

• 時(shí)間復(fù)雜度$O(m+n)$
• 空間復(fù)雜度$O(1)$

AC代碼

C++

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

Python

from typing import List

class Solution:
    def merge(self, nums1: List[int], l1: int, nums2: List[int], l2: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        l = l1 + l2 - 1
        l1, l2 = l1 - 1, l2 - 1
        while l2 >= 0:
            while l1 >= 0 and nums1[l1] > nums2[l2]:
                nums1[l] = nums1[l1]
                l, l1 = l - 1, l1 - 1
            nums1[l] = nums2[l2]
            l, l2 = l - 1, l2 - 1

同步發(fā)文于CSDN，原創(chuàng)不易，轉(zhuǎn)載經(jīng)作者同意后請(qǐng)附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132256535文章來源地址http://www.zghlxwxcb.cn/news/detail-645812.html

到了這里，關(guān)于LeetCode 0088. 合并兩個(gè)有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！