2

行ごとに並べ替えられた 2D nxn マトリックス内の要素を検索する方法。O(nlogn)各行のバイナリ検索を使用して、各行O(nlog(logn))の補間検索を使用して実行できます。解決O(n)策はありますか？

Constraint : 配列には整数が含まれます。

例 : 指定された 5x5 マトリックスで 32 を検索します。

0 5 6 8 42 98

-4 -1 3 21 455

-4 0 3 4 4

0 0 0 0 0

0 [32] 64 244 333

親切に助けてください。

4

2 に答える 2

-1

かなり古い投稿ですが、それでも。

右上隅または左下隅から開始します (任意の側を選択できます)。右上を選択するとします。キーを行列要素と比較します。

 if(key==matrix[i][j])
      return true;
   if(key<matrix[i][j])
         then move towards left(j--)
   else      //if the key is greater than the matrix element
         then move towards down (i++);

最悪の場合の時間の複雑さは、O(n+n) =O(n) のように 1 行と 1 列を移動する必要がある場合です。

于 2016-11-04T09:52:08.853 に答える