Solution 2
事情沒有想像中簡單啊!而且我題意也沒看清楚,題目很清楚寫著複雜度要是 O(log(m+n))
,
我們想一下,solution 1 可不可以降低複雜度?其實我們不用全部做完,只要額外加一個 count 去數是不是到第
k = (m+n)/2 個即可,這樣複雜度可以降到 O(k),
我們又可以想,中位數其實就是找第 k 大的元素,本題就變成在兩個陣列中找到第 k = (m+n)/2 大的數
我們先假設 A.length > k/2,這意思是會挑到A的元素
如果 A[k/2] < B[k/2] 表示