1

これはインタビューの質問です。ブール行列が与えられた場合、「真の」要素のみを含む最大の隣接する正方形の部分行列のサイズを見つけてください。

SOでこの質問を見つけましたが、答えがわかりませんでした。提案されたアルゴリズムは、対角線を左上から右下に移動し、線が進むにつれて「真の」要素の長方形を追跡します。

私の質問:

  • アルゴリズムで長方形を追跡するにはどうすればよいですか?
  • なぜ対角線を移動するのですか? 縦線/横線、またはその両方を移動するとどうなるでしょうか?
  • アルゴリズムの複雑さを計算する方法は?
4

1 に答える 1

4

あなたが投稿したリンクの答えを理解できません。そこに与えられた複雑さがあなたの問題に最適だとは思いません。(元の行列の要素数が であるO(N^(3/2)*logN)アルゴリズムがあると主張しています。)N=n*n

最大の正方部分行列の問題には、複雑さが要素数に比例する DP アルゴリズムがあります。

元の行列A[n][n]を とすると、行列 を見つけようとしていますB[n][n]。ここで、B[i][j]は、右下の要素が である最大の正方形の部分行列のサイズを示しますA[i][j]。そう

for (i = 0 ; i < n ; ++i)
  for (j = 0 ; j < n ; ++j) 
    if (A[i][j] == 0) B[i][j] = 0;
    else {
      if (B[i-1][j] != B[i][j-1]) {
        B[i][j] = min(B[i-1][j], B[i][j-1]) + 1
      } else {
        if (A[i-B[i-1][j]][j-B[i-1][j]] == 1)
          B[i][j] = B[i-1][j] + 1;
        else
          B[i][j] = B[i-1][j];
      }
    }

そして、最大の B[i][j] が答えです。

ps簡単にするために、配列の範囲をチェックしませんでした。範囲外の要素はゼロであると考えることができます。

于 2012-07-30T08:59:32.233 に答える