難度: Hard
類型: Array, Binary Search, Divide and Conquer
CPP程式下載: 4.cpp
==========================
算出兩個已排序矩陣合併後的中間值
其實這題並不難, 不知道為何難度是 Hard
==========================
前情題要:
==========================
思考方式:
1. 已知兩個矩陣的長度(m, n), 那合併矩陣的總長度是 m+n, 如果 (1+m+n) 是 2 的倍數, 那中間就是 (1+m+n)/2, 如果不能整除, 那就是拿 (1+m+n)/2 跟 (1+m+n)/2 + 1 位置的兩個數相加除以 2。
2. 就是兩個矩陣從小到大一個一個拿出來比較, 低的放進合併矩陣。(不必真的放, 題目不需要回傳新的合併矩陣, 所以只需要算新矩陣目前的個數, 以判斷到中間值了沒有。)
註: 要注意 m 或 n 可能有一個為 0, 分清楚邊界即可。
==========================
複雜度思考:
Time: O (log2(m+n))
Memory: O (1)
==========================
結果:
Runtime: 0 ms, Beats: 100%
Memory: 95.20 MB, Beats: 47.31%
