在排序的三维阵列搜索元素 [英] Searching element in sorted 3d array

问题描述

一个三维矩阵排序在所有三个维度给出了才   发现在它一个给定数目

A 3d matrix sorted in all three dimensions is given and we have to find a given number in it.

有关上述问题，我一直在思考这样的：三维数组改编[M] [N] [R] 会像一堆矩形，每个矩形（考虑改编[M] [N] [0] ）将有最大的元素作为最低最右边的元素（改编[M-1 ] [N-1] [0] ）。我们可以在 O（M + N），每个矩形内搜索：

For the above problem, I have been thinking this: The 3D array arr[m][n][r] would be like a stack of rectangles where each rectangle (consider arr[m][n][0]) would have the largest element as the lowest right-most element(arr[m-1][n-1][0]). We can search inside each rectangle in 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））。我说得对？

有没有人有任何其他的想法？什么是复杂性？

Does anyone have any other ideas? What would be the complexity?

推荐答案

您不能扩展线性复杂的2D解决了第三维，使得O（M + N + R）解决方案出来。三维阵列，分别排序在每个方向上，含有邻组（N ² ）元素，这是不相互之间的排序。例如，子阵列改编[I] [J] [K] ，其中 I + J + K =（M + N + R）/ 2 是完全无序。所以，你必须检查这种子阵列中的每个元素找到给定的数字。这证明，你能不能发明一种算法复杂度为O更好的（N ² ）（至少在M，N，和r不是很彼此不同）。这是证明的距离这个答案。

You cannot extend a linear complexity 2D solution to the 3rd dimension, making O(m+n+r) solution out of it. 3D array, sorted independently in each direction, contains groups of O(N²) elements, which are not ordered between each other. For example, sub-array arr[i][j][k] where i+j+k = (m+n+r)/2 is completely unsorted. So you have to inspect each element of such a sub-array to find given number. This proves that you cannot invent an algorithm with complexity better than O(N²) (at least when m, n, and r are not very much different from each other). This is just an extension of the proof from this answer.

下面是一个例子：

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

这个数组排序在所有3个维度。但是，这并不确定元件X，Y，Z的任何排序顺序。可以在（1，3），以这些元素的范围内分配任何值。虽然对于搜索的元素值为'2'，你必须检查所有的这些未分类值（x和y和z）。如果增加数组的大小，你看到的未分类值的数量可能会增加二次。这意味着搜索算法的最坏情况下的时间复杂度也要增加二次。

This array is sorted in all 3 dimensions. But this does not determine any sorting order for elements x,y,z. You can assign any values in the range of (1, 3) to these elements. And while searching for element with value '2' you have to inspect all these 'unsorted' values (x and y and z). If you increase size of the array, you see that the number of 'unsorted' values may increase quadratically. Which means worst case time complexity of the search algorithm should also increase quadratically.

您可以找到最小的数组大小（让它成为'R'），并为每个矩阵改编[*] [*] [K] 搜索在给定数O（M + N）的时间，这给了O（（M + N）* r）的时间复杂度。

You can find the smallest array size (let it be 'r'), and for each matrix arr[*][*][k] search given number in O(m+n) time, which gives O((m+n)*r) time complexity.

或者数组大小之一是比其他人大得多（ R＆GT;＆GT，M * N ），您可以使用二进制搜索常用3 [I] [J]。[*] （每个I，J），这使O（M * N *日志（R））的时间复杂度。

Or if one of the array sizes is much larger than others (r >> m*n), you can use binary search in arr[i][j][*] (for each i,j), which gives O(m*n*log(r)) time complexity.

这篇关于在排序的三维阵列搜索元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！