完全排序矩陣

Question

這個問題被要求在我面試的一個 -

M是在每一行和每一列排序的2D正乘n矩陣，矩陣的所有元素都不同。我需要一個O（n）算法 - 給定索引i，j，i0，j0作爲輸入，計算M小於M [i，j]且大於M [i0，j0]的元素數。我爲此嘗試了各種方法，但無法弄清楚。幫助將不勝感激。下一部分是找出O（nlogn）預期時間的M的中位數。

Answer 1

考慮一個矩陣作爲一組行。在每一行中都有最小和最大有效值的索引。如果知道這些索引，則可以計算O（1）中該行中有效值的數量。 （有效的意思是M [i，j]和M [i0，j0]之間的值）。

現在，矩陣被排序。讓我們取下界：（i，j）。

• 如果您想要查找上一行中最小有效值的索引，它必須位於（i，j）的右側。這是因爲在（i，j）上面必須有無效（太小）值。

• 如果您想要查找下一行中最小有效值的索引，它必須位於（i，j）（或其正下方）的左側。

因此，您需要遍歷矩陣遍歷最多2n個「步長」以找到每一行的下限索引。上限也是一樣。所以你的行走是O（n），然後計算每行有效值的數量是O（n），因此總時間是O（n）。

使用此算法可以解決中值問題。首先要注意的是，如果您計算以前問題的解決方案，則可以使用每行中邊界值的索引在線性時間內隨機選擇一個有效值。然後可以通過二分算法計算中值：

selection_find(M, i0,j0, i2,j2, K): 
    # Find K-th smallest number between M(i0,j0) and M(i2,j2) 
    # assumption: M(i0,j0)<M(i2,j2) 
    N := number of values between M(i0,j0) and M(i2,j2) 
    # assumption: k<N 
    Pick at random i1,j1 so that M(i0,j0)<M(i1,j1)<M(i2,j2) 
    L := number of values between M(i0,j0) and M(i1,j1) 
    if L==K: 
     The answer is M(i1,j1) 
    if L<K: 
     The answer is selection_find(M, i1,j1, i2,j2, K-L) 
    if L>K: 
     The answer is selection_find(M, i0,j0, i1,j1, K) 

median_find(M): 
    The answer is selection_find(M, 1,1, n,n, n²/2) 

每一步都需要O（N）。將會有O（log N 2）= O（2log N）= O（log N）個步驟（每個步驟應該將考慮的數值減半）。因此總的複雜度是O（NlogN）。