使用leetcode 怎么合并有序數(shù)組

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

§ 0x01 題目

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

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-sorted-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

§ 0x02 題目分析

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

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

一開始我的思路不太清晰。就想著從數(shù)組的右側(cè)開始處理，將兩個數(shù)組合并在一起。實現(xiàn)的時候發(fā)現(xiàn)有問題。

1  2 5 0 0
3 4

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

吃過午飯后，想了下，能否用分治策略呢，仔細一想發(fā)現(xiàn)可以。

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

1. 如果nums1的比較大，它就是整個結(jié)果中的最大值。將這個最大值放到最終數(shù)組的最后，也就是nums1[m+n-1]。問題模型變?yōu)?code>nums1 m-1 nums2 n。

2. 如果nums1的比較小或者等于。那么就可以把nums2的最大值，放到最終數(shù)組折最后。問題模塊變?yōu)?code>nums1 m nums2 n-1。

一開始沒考慮好極端場景。分治可以自然應(yīng)對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]
                }
        }
}

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