go語(yǔ)言題解LeetCode88合并兩個(gè)有序數(shù)組示例

更新時(shí)間：2022年12月30日 15:26:31 作者：劉09k11

這篇文章主要為大家介紹了go語(yǔ)言題解LeetCode88合并兩個(gè)有序數(shù)組示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

原題鏈接 :

88. 合并兩個(gè)有序數(shù)組

給你兩個(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]
解釋?zhuān)盒枰喜?[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]
解釋?zhuān)盒枰喜?[1] 和 [] 。
合并結(jié)果是 [1] 。

示例 3：

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

提示：

nums1.length == m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-10^9 <= nums1[i], nums2[j] <= 10^9 進(jìn)階：你可以設(shè)計(jì)實(shí)現(xiàn)一個(gè)時(shí)間復(fù)雜度為 O(m + n) 的算法解決此問(wèn)題嗎？

思路分析

代碼超簡(jiǎn)單，從后往前看，用兩個(gè)指針掃描兩個(gè)數(shù)組，邊比較邊存數(shù)，第三個(gè)指針指向nums1的末尾存數(shù)，存儲(chǔ)挪過(guò)來(lái)的大數(shù)。掃描指針移動(dòng)條件是，該數(shù)組有小的數(shù)。

退出條件是：nums2的索引到最左邊，說(shuō)明數(shù)的比較和移動(dòng)全部完成。需要注意的是i可能會(huì)因?yàn)閚ums2中的數(shù)都比較小，一直導(dǎo)致左超限。

AC 代碼

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 開(kāi)了三個(gè)指針，從后往前遍歷，二個(gè)掃描，一個(gè)存數(shù)
        int i = m-1, j = n-1, k = m+n-1;
        // 循環(huán)條件：當(dāng)nums2檢查完，整個(gè)工作也完成了。
        while (j >= 0)
        {
            // 注意執(zhí)行順序，先判斷i >= 0，再判斷數(shù)大小，否則會(huì)報(bào)索引超限錯(cuò)誤。
            if (i >= 0 && nums1[i] > nums2[j])
            {
                nums1[k] = nums1[i];
                i--;
            }
            // 執(zhí)行else條件：不滿(mǎn)足if中的任意一個(gè)條件。
            else
            {
                nums1[k] = nums2[j];
                j--;
            }
            k--; 
        }
    }
}

以上就是go語(yǔ)言題解LeetCode88合并兩個(gè)有序數(shù)組示例的詳細(xì)內(nèi)容，更多關(guān)于go 合并兩個(gè)有序數(shù)組的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: