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

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

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

題目描述

原題鏈接 :

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

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

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

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應(yīng)合并的元素，后 n 個元素為 0 ，應(yīng)忽略。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] 。
合并結(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] 。
注意，因為 m = 0 ，所以 nums1 中沒有元素。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è)計實現(xiàn)一個時間復(fù)雜度為 O(m + n) 的算法解決此問題嗎？

思路分析

代碼超簡單，從后往前看，用兩個指針掃描兩個數(shù)組，邊比較邊存數(shù)，第三個指針指向nums1的末尾存數(shù)，存儲挪過來的大數(shù)。掃描指針移動條件是，該數(shù)組有小的數(shù)。

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

AC 代碼

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

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

您可能感興趣的文章: