[LeetCode] 4. 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)).

Example 1:

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

The median is 2.0

Example 2:

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

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

<Solution>

這題要從兩個 sorted array 找到中位數，時間要求 O(log(m+n))

看到時間要求，就知道不能合併完 array 再找

解題的想法是，在合併的過程中，找到中位數就結束

因為中位數的位置可以從兩個 array 的長度先知道，要注意的是長度奇偶問題

想法如下

• 先求出中位數的位置，並判斷合併後的長度是奇數還是偶數
• 開始合併，每次從兩個 array 中抓比較小的那個出來
• 因為要處理長度是奇數偶數的問題，所以保留兩個值(目前和上一個)
• 當到達中位數的位置，結束迴圈，並根據長度是奇數偶數算出中位數

最後有看到一個神解法，速度會快很多

但是不是很懂他的邏輯，需要再研究