合併兩個排序陣列

Merge Sorted Array

搞笑版本：

硬是要用內建排序法整個陣列重新排序 O(nlogn)：先把第二陣列接進第一陣列。

這樣也可以過 Accepted。純粹好奇、惡搞，沒想到也可過。:D

回到正題。

首先我們要清楚兩個已經排序好的陣列合併，是雙指針倆倆比大小，從頭比到尾按照順序就排好了。(這是 Merge Sorting 合併排序法主要觀念)

這題關鍵問題在於要沿用第一陣列 (in-place)。如果新建第三陣列，來存放就沒什麼問題了 。(如果新建第三陣列還不會合併排序，那請左轉出去練習一下再回來吧)

一樣先分析問題：

• 因為沿用第一陣列後方的位置，所以無法正常從頭從小排

解決方案：

• 那就從尾巴從大開始排吧，這並不影響結果

我們硬是把 nums1 當作一種 nums3 然後從尾巴開始排。所以我們總共有三指針 nums1, nums2, nums1² 分別是 i, j, k 從尾巴開始。

為了簡化問題，我們視角放在假的第三陣列 k 指針上，移動 k 指針來問其值。

核心程式碼大概這樣：

while (k <= 0) {
  if (nums1[i] > nums2[j]) {
    nums1[k] = nums1[i];
    i--;
  } else {
    nums1[k] = nums2[j];
    j--;
  }
  k--;
}

只要加入邊界判斷，無腦就完成了 Accepted：

另外其實 k 指針可以省略，透過 i+j 得知，不過為了簡化問題，當作真有三個指針操作會稍微簡單一點。

而且這有一部份改善的空間，如果第一陣列都小於第二陣列，那麼第二陣列會先結束 (j == 0) 。但是仍會繼續檢查第一陣列，那就是一種浪費了。這部分就不解說了。不過此優化仍不影響複雜度。

衍伸議題 — 如何減少條件判斷

減少條件判斷有些許優點：

• 核心演算法可讀性增高
• 減少出錯腦殘眼殘率

依據這題，可以透過墊一層最小值，來避免接觸邊界處理 0 based 問題。

ref. https://en.wikipedia.org/wiki/Merge_sort