在已排序的三維數組中搜索元素

給出了在所有三維中排序的三維矩陣，我們必須找到找到其中的給定數字。在已排序的三維數組中搜索元素

對於上述問題，我一直在想這樣的：三維陣列arr[m][n][r]會像矩形的疊層，其中每個矩形（考慮arr[m][n][0]）將具有最大的元素作爲最低最右邊的元件（arr[m-1][n-1][0]）。我們可以在每個O(m+n)矩形內搜索：

int row = 0; 
int col = N-1; 

while (row < M && col >= 0) 
{ 
    if (mat[row][col] == elem) 
    { 
    return true; 
    } 
    else if (mat[row][col] > elem) 
    { 
    col--; 
    } 
    else 
    { 
    row++; 
    } 
}

我想這也同樣可以擴展到第三維，從而使其成爲一個線性複雜的解決方案（O(m+n+r)）。我對嗎？

有沒有人有任何其他想法？什麼是複雜性？

來源

2012-07-21 Rndm

你可以可能會在每個維度上連續使用簡單的二進制搜索（3x）。這將產生O（log（m）+ log（n）+ log（r））。深度爲3的B樹在相同的複雜度下基本上會做同樣的事情。 – JimmyB 2012-07-21 14:36:15

您無法將線性複雜度2D解決方案擴展到第3維，使O（m + n + r）解決方案不在其中。三維數組，在每個方向上獨立排序，包含O（N ）元素的組，它們彼此之間沒有排序。例如，子陣列arr[i][j][k]其中i+j+k = (m+n+r)/2是完全未排序的。所以你必須檢查這樣一個子數組的每個元素來查找給定的數字。這證明你不能發明一個複雜度比O好的算法（至少當m，n和r彼此沒有太大差異時）。這只是this answer的證明的延伸。

下面是一個例子：

k=0: |1 x| k=1: |z 3| 
    |y 3|  |3 4|

該數組中的所有3個維度排序。但是這並不能確定元素x，y，z的排序順序。您可以將（1，3）範圍內的任何值分配給這些元素。在搜索值爲'2'的元素時，您必須檢查所有這些「未排序」值（x和y和z）。如果增加數組的大小，則會看到'未排序'值的數量可能會以二次方式增加。這意味着搜索算法的最壞情況時間複雜度也應該以二次方式增加。

您可以找到最小的數組大小（讓它爲'r'），並且對於每個矩陣arr[*][*][k]在O（m + n）時間搜索給定數字，這會給出O（（m + n）* r）時間複雜。

或者數組大小的一個是比其他人（r >> m*n）大得多，你可以在arr[i][j][*]使用二進制搜索（每個I，J），這給Ô（M ñ日誌（R））的時間複雜度。

來源

2012-07-21 15:34:32

我看了你在回答中給出的鏈接，並明白在2d中，我們不能達到小於O（n）的效果，但對於3d，arr [i] [j] [k] ' - >這將是1個元素的權利，而不是3d的子數組？ – Rndm 2012-07-22 04:20:37

@shg：'arr [i] [j] [k]'不僅僅是一個元素：這裏i，j，k不是常量，它們是約束變量，其中'i + j + k =（m + n + R）/ 2'。這個限制使得3D切片不在3D數組中。 – 2012-07-22 08:11:25

如果內存消耗不是一個大問題，您可以將您的數組複製到單個一維對的一維數組中，然後按值排序該數組，並使用O（log（n + m + r）））的複雜性。但是最初的排序會花費O（（n + m + r）* log（n + m + r））來定義總的算法複雜度。

我想感謝3D數組在每個維上排序的事實，可以找到一些算法將它轉換爲比O（（n + m + r）* log（n + m）更快的排序1D數組） + r）），但我不知道這樣的事情。也許Chiyou試圖解釋這一點。

來源

2012-07-21 16:47:16

我可以想到一個遞歸解決方案，它將在理論上是一個lograthmic。

說n是你在一個立方體NxNxN尋找的數字。該立方體從東到西，從北到南，從上到下依次排列。這樣極端東北部的數字最小，極端西南部的數字最大。

選取立方體中心的數字。如果這個數字等於n，那麼我們找到了這個數字。如果這個數字大於n，那麼我們可以忽略所有位於西南底的數字，因爲這些數字都會大於n。這些數字是立方體的1/8。現在我們可以輕鬆地將立方體的剩餘部分拆分爲7個立方體並重復該過程。

類似的，如果這個數字小於n，我們可以忽略所有數字在東北部。

Point find(int[][][]matrix, int N, int n) 
{ 
    if(N == 0) 
    { 
     return null; 
    } 

    int x = matrix[N/2][N/2][N/2]; 
    if(x == n) 
     return new Point(N/2, N/2, N/2); 
    else if (x > n) 
    { 
     for(Matrix m: SplitTheCubeInto8CubesAndIgnoreSouthWestBottomCube(matrix)) 
     { 
      if((p = find(m, N/8, n)) != null) 
       return p; 
      else 
       return p; 
     } 
    } 
    else 
    { 
     for(Matrix m: SplitTheCubeInto8CubesAndIgnoreNorthEastTopCube(matrix)) 
     { 
      if((p = find(m, N/8, n)) != null) 
       return p; 
      else 
       return p; 
     } 
    } 
}

如下複雜性可以表示爲：。 T（M）= 7 * T（M/8）+ 1（M是臥在立方體點的總數目M = N * N * N.在每個比較中，我們剩下7個立方體的M/8尺寸） O = ln（M）[ln是基於8/7] 或O = ln（N）

來源

2014-01-14 02:42:29

在已排序的三維數組中搜索元素

回答

相關問題