查找兩個排序數組的合併數組中的位數

假設我們有2個大小爲n和m的整數數組。找到所有m + n數字的中位數的最佳方法是什麼？查找兩個排序數組的合併數組中的位數

很容易做到這一點與log(n) * log(m)複雜性。但我想在log(n) + log(m)時間解決這個問題。那麼有沒有解決這個問題的建議？

2017-05-31 Ju Bc

我找不到一個很棒的副本，但有幾十個[很容易找到]（https://www.google.com/search?q=median+of+2+sorted+array）有關這個帖子在[so]和其他地方，比如[this]（https://stackoverflow.com/questions/18790467/median-of-two-sorted-arrays）和[this]（https://stackoverflow.com/questions/ 13222934 /中位數爲2的排序陣列-的-不同程長度）。顯示沒有研究努力。 – Dukeling

說明

這個問題的關鍵點是通過比較剩餘甲乙的中值，以忽略A和B的每一步的半部分遞歸：

if (aMid < bMid) Keep [aMid +1 ... n] and [bLeft ... m]  
else Keep [bMid + 1 ... m] and [aLeft ... n] 
// where n and m are the length of array A and B

如下面的：時間複雜度爲O(log(m + n))

public double findMedianSortedArrays(int[] A, int[] B) { 
    int m = A.length, n = B.length; 
    int l = (m + n + 1)/2; 
    int r = (m + n + 2)/2; 
    return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r))/2.0; 
} 

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) { 
    if (aStart > A.length - 1) return B[bStart + k - 1];    
    if (bStart > B.length - 1) return A[aStart + k - 1];     
    if (k == 1) return Math.min(A[aStart], B[bStart]); 

    int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE; 
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];   

    if (aMid < bMid) 
     return getkth(A, aStart + k/2, B, bStart, k - k/2); // Check: aRight + bLeft 
    else 
     return getkth(A, aStart, B, bStart + k/2, k - k/2); // Check: bRight + aLeft 
}

希望它有幫助！讓我知道你是否需要更多的解釋。

來源

2017-05-31 04:30:56

-2

是的，這可以完成。給定兩個數組，A和B，在最壞的情況下，您必須首先執行二進制搜索A，然後，如果失敗，則在B的二進制搜索中查找中位數。在二進制搜索的每一步中，檢查當前元素是否實際上是合併的A+B數組的中位數。這種檢查需要不斷的時間。

讓我們來看看爲什麼這樣的檢查是恆定的。爲了簡單起見，我們假設|A| + |B|是一個奇數，並且兩個數組中的所有數字都不相同。稍後可以通過應用通常的中值定義方法（即，如何計算包含重複數組的數組的中值或具有偶數長度的數組的中值）來刪除這些限制。無論如何，鑑於這一點，我們可以確定的是，在合併後的陣列中，右邊和左邊的實際中位數都會有個元素。在A的二進制搜索過程中，我們知道當前元素x在數組A（讓它爲i）的索引。現在，如果x滿足條件B[j] < x < B[j+1]，其中i + j == (|A| + |B| - 1)/2，那麼x是你的中位數。

整體複雜度爲O(log(max(|A|, |B|))時間和O(1)內存。

來源

2017-05-31 03:04:58 iehrlich

關於downvotes的一些評論非常感謝。 – iehrlich

你的算法似乎是畸形的，我不知道它是否會實際返回A + B的中位數 – JacaByte

@JacaByte這不是「畸形」的定義。反例就是。 – iehrlich

取出列表A中的中間元素並將其稱爲a。將a與列表B中的中心元素進行比較。讓我們稱它們爲b1和b2（如果B具有奇數長度，那麼恰好在您拆分b的位置取決於您對偶數長度列表的中位數的定義，但該過程幾乎相同）。如果b1 ≤ a ≤ b2那麼a是合併數組的中位數。這可以在一段時間內完成，因爲它只需要兩次比較。

如果a大於b2，則我們將A的上半部分添加到B的頂部並重復。 B將不再被排序，但沒關係。如果a小於b1，那麼我們將A的下半部分添加到B的底部並重復。這些將最多重複log（n）次（如果中位數更早發現，然後停止）。

這可能不會找到中位數。如果是這種情況，則中位數在B中。如果是這樣，則執行與A和B顛倒相同的算法。這將需要log（m）迭代。總的來說，您將執行恆定時間操作的最多2 *（log（n）+ log（m））迭代，因此您已按log（n）+ log（m）時間順序解決了問題。

這與iehrlich給出的答案基本相同，但寫得更明確。

來源

2017-05-31 03:58:45 tuerda

Here's a very good solution I found in Java on Stack Overflow.這是一種在兩個數組中找到K和K + 1個最小項的方法，其中K是合併數組的中心。

如果你有一個函數來找到兩個數組的第K項，那麼找到這兩個數的中值很容易;

計算第K個和第K + 1項X和Y

的加權平均水平，但那麼你就需要一種方法來找到兩個列表的第K項; （請記住，我們現在正在一個索引）

如果X包含零個項目，那麼X的第K個最小項和Y爲Y
的第K個最小項
否則，如果滿足K == 2則X和Y的第二小項目是X和Y的最小項目中的最小項目（min（X [0]，Y [0]））
否則;

i。令A爲min（長度（X），K/2）

ii。令B爲min（長度（Y），K/2）

iii。如果X [A]> Y [B]從步驟1開始遞歸到X，Y'，其中Y的所有元素都從B到Y的結束，並且K'= K-B，否則用X'遞增所有元素從A X到的X，Y和K」 = K結尾的 - 一個

如果我發現的時候，明天我會覈實，該算法在Python可以作爲說明並提供示例源代碼，它可能會有一些錯誤的錯誤。

來源

2017-05-31 04:44:09 JacaByte

查找兩個排序數組的合併數組中的位數

回答

相關問題