在已排序的 3d 数组中搜索元素

Question

给出了一个在所有三个维度中排序的 3d 矩阵，我们必须在其中找到一个给定的数字。

对于上述问题，我一直在思考：3D 数组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)）。我对吗 ？

有没有人有其他想法？复杂性如何？

Answer 1

您不能将线性复杂度 2D 解决方案扩展到第 3 维，从而使 O(m+n+r) 解决方案从中脱颖而出。在每个方向上独立排序的 3D 数组包含 O(N ² ) 组元素，它们之间没有排序。例如，子数组arr[i][j][k]wherei+j+k = (m+n+r)/2是完全未排序的。所以你必须检查这样一个子数组的每个元素才能找到给定的数字。这证明您无法发明一种复杂度比 O(N ² )更好的算法（至少当 m、n 和 r 彼此相差不大时）。这只是这个答案的证明的扩展。

下面是一个例子：

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））的时间复杂度。