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

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

給你兩個按 非遞減順序 排列的整數數組?nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。

請你 合并 nums2 到 nums1 中，使合并后的數組同樣按 非遞減順序 排列。

注意：最終，合并后數組不應由函數返回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，后 n 個元素為 0 ，應忽略。nums2 的長度為 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] 。
合并結果是 [1,2,2,3,5,6] ，其中斜體加粗標注的為 nums1 中的元素。

示例 2：

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

示例 3：

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

?

提示：

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

?

進階：你可以設計實現一個時間復雜度為 O(m + n) 的算法解決此問題嗎？

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

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

怎么原地修改呢？nums1后面全是$0$，而這些地方本來應該是“大數”，所以我們使用兩個指針，從$nums1$和$nums2$的大數區域往前指，每次將二者較大的那個放到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$的指針指完了，任務完成，得到$[1,2,3,6]$

• 時間復雜度$O(m+n)$
• 空間復雜度$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 Listclass 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 - 1l1, l2 = l1 - 1, l2 - 1while l2 >= 0:while l1 >= 0 and nums1[l1] > nums2[l2]:nums1[l] = nums1[l1]l, l1 = l - 1, l1 - 1nums1[l] = nums2[l2]l, l2 = l - 1, l2 - 1

同步發文于CSDN，原創不易，轉載經作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132256535