2

3次元すべてでソートされた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++;
  } 
}

同様に3次元に拡張できると考えていたので、線形の複雑さのソリューションになりました（O(m+n+r)）。私は正しいですか？

他に何かアイデアはありますか？複雑さは何でしょうか？

4

3 に答える 3

5

線形複雑度の2Dソリューションを3次元に拡張して、それからO（m + n + r）ソリューションを作成することはできません。各方向に独立してソートされた3D配列には、O（N 2）要素のグループが含まれています。これらの要素は互いに順序付けられていません。たとえば、完全にソートされていないarr[i][j][k]サブ配列。i+j+k = (m+n+r)/2したがって、そのようなサブ配列の各要素を調べて、指定された数を見つける必要があります。これは、O（N 2 ）よりも複雑なアルゴリズムを発明できないことを証明しています（少なくとも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）を検査する必要があります。配列のサイズを大きくすると、「ソートされていない」値の数が2倍に増える可能性があることがわかります。つまり、最悪の場合の検索アルゴリズムの時間計算量も2倍に増加するはずです。

最小の配列サイズ（'r'とします）を見つけることができ、各行列に対してarr[*][*][k]、O（m + n）時間で指定された数を検索します。これにより、O（（m + n）* r）時間計算量が得られます。

または、配列サイズの1つが他のサイズよりもはるかに大きい場合（ ）、 （各i、jに対して）r >> m*n二分探索を使用できます。これにより、O（m n log（r））の時間計算量が得られます。arr[i][j][*]

于 2012-07-21T15:34:32.370 に答える
1

メモリ消費が大きな問題ではない場合は、配列をペアの単一の1D配列にコピーしてから、この配列を値で並べ替えて、O（log（n + m + r））の複雑さでバイナリ検索を実行できます。ただし、最初の並べ替えにはO（（n + m + r）* log（n + m + r））が必要であり、これによりアルゴリズム全体の複雑さが定義されます。

3D配列が各次元でソートされているという事実に感謝すると、O（（n + m + r）* log（n + m + r））よりも速くソートされた1D配列に変換するアルゴリズムを見つけることができると思います。 、しかし私はそのようなことを知りません。たぶん、Chiyouはこれを説明しようとしました。

于 2012-07-21T16:47:16.893 に答える
1

理論的には対数的である再帰的な解決策を考えることができます。

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。各比較で、次のようになります。それぞれM/8サイズの7つの立方体が残っています）O = ln（M）[lnは8/7のベースにあります]またはO = ln（N）

于 2014-01-14T02:42:29.927 に答える