最後更新於 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)
要思考的特殊情況有:
nums2
陣列為空 -> 不用做任何處理。nums1
陣列為空 -> 直接將 nums2 照搬到 nums1。- 否則將 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--]; } } } }
Latest posts by pluto (see all)
- 解決 preact-router 資源請求路徑錯誤的問題 - 2022 年 6 月 24 日
- [楓之谷私服] 潮流轉蛋機 NPC 腳本優化 - 2022 年 6 月 19 日
- [楓之谷私服] 簡單的飛天椅子(坐騎)改法 v120 - 2022 年 6 月 19 日