[解題筆記] LeetCode: Median Of Two Sorted Arrays (Hard)

前言

一直以來都覺得 Medium 的題目好像就蠻難的，所以也沒有刻意想去挑戰 Hard，這次是上次的題目寫完接著寫下一題，寫完覺得沒有真的很難，也許這題是例外吧，總之順手紀錄一下心得。

題目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

分析

題目的 the median 用粗體標示，對這個單字沒什麼印象於是稍微查了一下，原來是指 中位數。來自維基百科的定義：

⋯⋯如果數據的個數是奇數，則中間那個數據就是這群數據的中位數；如果數據的個數是偶數，則中間那2個數據的算術平均值就是這群數據的中位數。

搭配題目的要求，就是希望取得兩個陣列合併後的中間那一項的值，如果是陣列長度是偶數那就是中間兩項的平均。到這邊我想到兩種做法：

1. 看到兩個陣列合併就想到 Merge Sort，但仔細看題目發現 nums1 與 nums2 都是 sorted array，所以只靠 pointer 就可以合併，合併後取得中間值。
2. 直接把兩個陣列合併起來後 sort()，然後取得中間值。

Pointer

var findMedianSortedArrays = function(nums1, nums2) {
    if ((nums1.length + nums2.length) <= 1) {
      return nums1[0] || nums2[0] || 0
    }
    
    let mergedArray = []
    let i = 0, j = 0
    
    while (i < nums1.length && j < nums2.length) {
      if (nums1[i] < nums2[j]) {
        mergedArray.push(nums1[i]);
        i++;
      } else {
        mergedArray.push(nums2[j]);
        j++;
      }
    }

    if (i < nums1.length) {
      mergedArray.push(...nums1.slice(i));
    }
    if (j < nums2.length) {
      mergedArray.push(...nums2.slice(j));
    }

    return mergedArray.length % 2 === 0
      ? (mergedArray[mergedArray.length / 2 - 1] + mergedArray[mergedArray.length / 2]) / 2
      : mergedArray[(mergedArray.length - 1) / 2]
}

算是簡化版的 merge sort 寫法，while loop 比較 nums1 與 nums2 的大小，當 i, j 其中一個指針已經比較完，代表另一個數列剩下的數都是更大的值，直接推進 mergedArray 就完成兩個數列的合併。需要注意的是 nums1 與 nums2 必須是 sorted array，如果兩個陣列都沒有排序過，就要使用 merge sort。

Array.sort()

var findMedianSortedArrays = function(nums1, nums2) {
  let merged = [...nums1, ...nums2]
  merged.sort((a, b) => a - b)

  return merged.length % 2 === 0
    ? (merged[merged.length / 2 - 1] + merged[merged.length / 2]) / 2
    : merged[(merged.length - 1) / 2]
}

簡單快速，覺得好像沒什麼好紀錄的。有時候看過一些題目有明確限制不能使用原生的 methods，但這題沒有所以直接用 sort() 也可以成功的 submission。

After Submission

Submission 之後看到的效能數字其實沒有很好，大概都在 50% 以下。但是同一個解答多提交幾次發現效能數字落差蠻大的，我猜可能是有 random test case。我還是去看了一下 Runtime 與 Memory 效能較優異的寫法，發現 Runtime 表現較好的就是使用 Array.sort()，發現 Runtime 表現較好的就是 Pointer 的寫法，而且跟我寫的邏輯幾乎一樣，沒有太大的差異。

總結

思考的時候其實有點懷疑，題目是給兩個 sorted array，會不會給兩個 random array 更能符合 Hard 的等級。如果是 random array 其實就很明確是想考 Merge Sort？不過其實不管有沒有先 sorted，第二種方式其實都能完成功能。

題外話，這讓我想到一個有趣的問題：JavaScript 到底是用哪一種演算法實作 sort()？結果讓我發現了一個新名詞 TimSort。稍微看了一下別人的分析，很有趣！但應該不是現階段的我能夠 handle 的，有機會再來讀看看 source code。

參考資料

• Median Of Two Sorted Arrays @LeetCode