Neil的部落格

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:

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

這題想了8小時結果還是想不出來，只能參考連結中的作法。

https://www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/

看完上面連結的教學後，才發現自己的方向差太遠了。 完全沒有想過是用binary search的概念去解題。

看來排序和搜尋的演算法需要好好複習一番了。

整題主要的核心在於

Step1.如何把 "陣列A" 和 "陣列B" 混再一起，在切割出兩等份的群組。

Step2.如何將切出的群組找出有一個群組所有的元素皆是小於另一個群組的任一元素。

簡單來講就是 假設群組A是最小  群組B是最大   那麼從群組B隨邊挑一個元素"皆"必須大於群組A。

在這樣的條件達成時，中位數便呼之而出。  ---->  成功條件

問題在於如何找出群組A和群組B 分別在陣列中的切割點。是屬於哪個陣列。

連結中的做法將設計兩個pointer i , j 

在正常情況下，i 將指向在陣列A中的群組A      j 將指向在陣列B中的群組A

--------

AABB   --->陣列A

AABB   --->陣列B

--------

以上面的例子 i將指向陣列A從左邊數來第二個A

j將指向陣列B從左邊數來第二個A

此時A元素皆在最小群組中，B元素皆在最大群組中。

我們需要找出他們的交界點是誰??

故我們會使用Max、Min函數去尋找

Max去尋找最小群組在陣列A與陣列B中，誰是最大的元素

Min去尋找最大群組在陣列A與陣列B中，誰是最小的元素

透過此特性便可以找到最大群組與最小群組的交界點。

在這一題最關鍵的點還是在於怎麼去想出  i pointer 在陣列A中的移動 還有 j pointer 在陣列B中的移動

關鍵的公式

需要有 low high  陣列A的數量 =n    陣列B的數量 = m

low = 0   high = n

i = ( low + high )  /  2

j = ( n + m + 1 ) / 2  -  i  

j公式裡面的 +1究竟代表什麼呢!!!?

我一開始也搞不懂，但是多了 + 1 好處多多!!!   因為兩個陣列的數量  n + m 可能會是 even or odd

在odd 的時候 可以透過 +1 幫助你要取最小群組的元素時  最小群組時可以取到較多偏小的元素

也就是說假設在odd的情況下，你的最小群組數量  == (最大群組數量 + 1)

然後另外一點需要特別注意，放在第一順位的陣列A如果數量小於放在第二順位的陣列B，則位置需要調換。

也就是說如果有如下兩個陣列

int[]  A{1, 2, 3, 4}

int[]  B{1,3,4,6,7,8}

i必須當B陣列的pointer

j必須當A陣列的pointer

不然套用到公式會產生錯誤