使用leetcode 怎么合并有序數組

使用leetcode 怎么合并有序數組，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

§ 0x01 題目

給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序數組。

初始化 nums1 和 nums2 的元素數量分別為 m 和 n 。你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來自 nums2 的元素。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-sorted-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

§ 0x02 題目分析

好久沒有做過算法題目了。趁清明假期有時間，看陳皓的《極客時間》欄目里推薦刷點leetcode，就來了，剛好是這一道。

這道題是基礎題，合并有序數組這樣的邏輯是很常見的。比如，歸并排序中，最后合并的兩個子數組就是有序數組。 最容易想到的就是冒泡和插入排序，但這樣的實現顯然不是最優的，因為沒有利用到兩個數組是有序的特性。

一開始我的思路不太清晰。就想著從數組的右側開始處理，將兩個數組合并在一起。實現的時候發現有問題。

1  2 5 0 0
3 4

如上面的兩個數組，當處理完5之后，5留下的空位不知道要怎么處理。寫了半天也沒有想出來怎么處理。查了下有一篇文章的實現挺簡單的，不過思路一時間接受不了。https://blog.csdn.net/aka_xyz/article/details/114269364

吃過午飯后，想了下，能否用分治策略呢，仔細一想發現可以。

一開始處理的問題模型為：nums1 m nums2 n。 先比較下nums1和nums2的最大值，也就是最右邊的值。

1. 如果nums1的比較大，它就是整個結果中的最大值。將這個最大值放到最終數組的最后，也就是nums1[m+n-1]。問題模型變為nums1 m-1 nums2 n。

2. 如果nums1的比較小或者等于。那么就可以把nums2的最大值，放到最終數組折最后。問題模塊變為nums1 m nums2 n-1。

一開始沒考慮好極端場景。分治可以自然應對num2中所有值比nums1大的場景，但處理不了num2中所有值都比nums1小的場景。所以要單獨處理。

func merge(nums1 []int, m int, nums2 []int, n int) {
        pos := m + n - 1
        p1 := m - 1
        p2 := n - 1
		// 問題模型由p1 p2 nums1 nums2定義
        for p2 >= 0 && p1 >= 0 {
                if nums1[p1] > nums2[p2] {
                        nums1[pos] = nums1[p1]
                        p1--
                        pos--
                } else {
                        nums1[pos] = nums2[p2]
                        p2--
                        pos--
                }
        }

		// 處理極端場景
        if p1 < 0 && p2 >= 0 {
                for i := 0; i <= p2; i++ {
                        nums1[i] = nums2[i]
                }
        }
}

看完上述內容，你們掌握使用leetcode 怎么合并有序數組的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！