Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Median of Two Sorted Arrays]，這在 LeetCode 算是比較困難的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

** Example 1 **

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

** Example 2 **

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

自己解法

這題目看起來很簡單，主要會給你兩個已排序的陣列，接著透過程式去找出中位數，但其實蠻深奧，主要在於時間複雜度問題，一開始我先用我最熟悉的方式解決他，裡面大部分的內容可以直接使用Javascript內建的韓式解決如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // 兩個陣列進行合併並且排序。
  const numsList = nums1.concat(nums2).sort();
  const numsLength = numsList.length;
  const midNumber = numsLength / 2;
  // 判斷基數或偶數
  if (numsLength % 2 === 1) {
    // 取得中位數
    return numsList[Math.ceil(midNumber) - 1];
  } else {
    // 取得兩值的中位數
    return (numsList[midNumber - 1] + numsList[midNumber]) / 2;
  }
};

提交之後，針對sort部分遇到負數似乎會發生問題，這部分我也丟到CodePen進行測試所以我們再重新改寫一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // 兩個陣列進行合併並且排序，另外如果要判斷負數需要改寫sort函式
  const numsList = nums1.concat(nums2).sort(function(a,b) { return a - b; });
  const numsLength = numsList.length;
  const midNumber = numsLength / 2;
  // 判斷基數或偶數
  if (numsLength % 2 === 1) {
    // 取得中位數
    return numsList[Math.ceil(midNumber) - 1];
  } else {
    // 取得兩值的中位數
    return (numsList[midNumber - 1] + numsList[midNumber]) / 2;
  }
};

測試結果竟然通過了，不過執行時間相對就差太多，排名約在 36%左右，主要問題會是在因為在Javascript內建的函式跑的時間會比較久，所以這次需要重新思考不透過既有的函式去改寫這塊。