0

これはインタビューの質問です：

ビットの m 行列を指定すると、行列内で形成される最大の X を見つけ、その X の対角線のサイズを返します。X は、1 つの 1 を共有する 2 つの同じサイズの対角線として定義されます。

たとえば、行列は次のとおりです。

00100001
00010010
00001100
00001100
00010010
00100001

中央部分は単一の 1 を共有しないため、指定された X は無効であるため、サイズ 1 が返されます。 一方、次の行列は、

101
010
101

対角線が 3 であるため、値 3 を返します。このようなプログラムを作成します。

ここで説明した最初の解決策は理解していますが、この問題を解決するためのより効率的な方法があるかどうか疑問に思っています。考え？

4

1 に答える 1

2

時間の複雑さに関して、より良い漸近的な解決策はありません。より弱い問題は、行列に 1 セルが含まれているかどうかを確認することです。この問題では、明らかにすべてのセルにアクセスする必要があり、O(nxm) が得られます。これは、O(nxm) を持つ元の問題の下限です。Qed。

于 2013-09-07T08:05:16.273 に答える