[JAVA] LeetCode 88. Merge Sorted Array 合併排序陣列

最後更新於 2022 年 4 月 8 日

題目

有兩個整數陣列 nums1 和 nums2，兩個整數 m, n 分別代表 nums1 , nums2 中非 0 的個數，目標是合併nums1和nums2成單一陣列並且由小到大排序。

要注意的是，我們不需要輸出任何東西，只需要將完整結果儲存在 nums1 即可。

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

思路

我們需要有三個索引，i 用於從後往前遍歷 nums1(不含0)、j 用於從後往前遍歷 nums2、k 用於從後往前遍歷 nums1。

int i = m - 1; // 指向 nums1 最後(非0)
int j = n - 1; // 指向 nums2 最後
int k = m + n - 1; // 指向 nums1 陣列最後(含0)

要思考的特殊情況有：

1. nums2陣列為空 -> 不用做任何處理。
2. nums1陣列為空 -> 直接將 nums2 照搬到 nums1。
3. 否則將 nums1[i] 與 nums2[j] 做比較，將較大的值放入 nums1[k]，比完一個數和放完一個數記得往前移動索引。

// 從 nums1(非0) 與 nums2 最後開始往回比較 , 比較大的值從 nums1 陣列最後開始往回擺
while(j >= 0) {
     if(i >= 0){
          nums1[k--] = nums2[j] > nums1[i] ? nums2[j--] :nums1[i--];
     } else {
          nums1[k--] = nums2[j--];
     }
}

程式碼

class Solution {
    
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // 指向 nums1 最後(非0)
        int j = n - 1; // 指向 nums2 最後
        int k = m + n - 1; // 指向 nums1 陣列最後(含0)
        
        // 從 nums1(非0) 與 nums2 最後開始往回比較 , 比較大的值從 nums1 陣列最後開始往回擺
        while(j >= 0) {
            if(i >= 0){
                nums1[k--] = nums2[j] > nums1[i] ? nums2[j--] :nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
    }
}

• About
• Latest Posts

pluto

懶癌末期患者，正以經營博客治癒。

Latest posts by pluto (see all)

• 解決 preact-router 資源請求路徑錯誤的問題 - 2022 年 6 月 24 日
• [楓之谷私服] 潮流轉蛋機 NPC 腳本優化 - 2022 年 6 月 19 日
• [楓之谷私服] 簡單的飛天椅子(坐騎)改法 v120 - 2022 年 6 月 19 日

相關文章:

[楓之谷私服]小遊戲系列NPC腳本(2) – BJ、GEMS、OX遊戲、Mastermind、猜數字 [楓之谷私服]小遊戲系列NPC腳本(1) – 21點、寶石連線、排列組合、踩地雷、老虎機 GraphQL + Express + MySQL 實戰學習筆記 Golang學習筆記：陣列(Array)與切片(Slice) 2022免費前端初學者學習資源(網站、電子書、趨勢追蹤、工具資源、面試題目…等)