在已排序的三维数组中搜索元素

给出了在所有三维中排序的三维矩阵，我们必须找到找到其中的给定数字。在已排序的三维数组中搜索元素

对于上述问题，我一直在想这样的：三维阵列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

在已排序的三维数组中搜索元素

回答

相关问题