[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--];
            }
        }
        
    }
}

4e52d54f6bc42abb41d26eb5b0df6517?s=250&d=wavatar&r=g [JAVA] LeetCode 88. Merge Sorted Array 合併排序陣列
0 0 評分數
Article Rating
訂閱
通知
guest
0 Comments
在線反饋
查看所有評論