3

1 と 0 で満たされた 2 次元行列が与えられます。連続するすべての 1 がすべての 0 の前にあると見なされます。連続する 1 の最大数を見つける必要があります。

すべての行にバイナリ検索を適用して、その行の最後の 1 の最後のインデックスを 0 が始まる前に取得できるという解決策を作成しました。1 の数はそのインデックス +1 になります。したがって、すべての行でこれを行うことができます。したがって、複雑さは O(mlogn) になり、m は no です。行数で、n は番号です。列の。これに対するより良い解決策はありますか?

4

7 に答える 7

3

最大値のみに関心があるため、すべての行のスイッチの位置を見つける必要はありません。

最初の行のスイッチ位置 k(0) が見つかった後、位置 k(0) から始まる 2 番目の行を検索し、それが 0 の場合、2 番目の行には最長のシーケンスが含まれていないため、どこを無視してもかまいません。それは実際にあります。これにより、最悪の場合の時間の複雑さは改善されませんが、平均的な場合は改善されます。

于 2012-04-07T13:03:52.217 に答える
3

O(n+m) アルゴリズムの要点はこれです。

マトリックスをグリッドとして想像してください。

左上隅から始めます。

1 の場合は、右に移動します。それ以外の場合は下に移動します。

最後の行を通過するまでこれを続けます。

次に、x座標は1の最大数です。

すべて 1 の行がある場合は、最後の列を 1 つ越えて移動できます。アルゴリズムはこれに対応する必要があります。

于 2012-04-07T13:21:48.943 に答える
3

O(n + m)で実行できます。

0 に等しい curmax から始めます。

次に、行を 1 つずつ処理します。その行に少なくとも curmax のものがある間、curmax を増やします。つまり、curmax 値が 1 かどうかをチェックします。

すべての行が処理された後、答えは curmax-th になります。

これは O(n+m) で機能します。

O(m*logn) より速いでしょうか? 場合によります。m が n/(log(n) - 1) より小さい場合、実際には O(m*log n) よりも長く、それ以外の場合は複雑さの点でより速く動作します。
時間を概算するとき、定数を考慮することは別の問題です。したがって、大きさが同じ n と m の場合、これはより速くなります。異なる場合、選択肢は 1 つだけです。両方を試して、より良いものを選んでください。

于 2012-04-07T13:11:26.173 に答える
1
1     bool matrix[100][200];
2     int max = 0, count, x;
3     
4     for(int y=0;y<100;y++){
5         count = 0;
6         x=max; // This would optimize the search times!
7         for(;x<200;x++){
8             if(matrix[y][x] == 0 && count>max){
9                max=count;
10            }
11            else count++;
12        }
13        if(x == 199)break; // Optimization - the end reached
14    }
15
16    // Now the max var contains the maximum number of 1's of a single row in all columns.

各行を歩く代わりに、既知の位置をスキップするだけです。この最適化は6行目に実装されています。

于 2012-04-07T13:15:25.780 に答える
0

連続してチェックして、前の列で停止した位置から次の列を開始するだけです。0 の場合は次の行に進み、それ以外の場合は行のチェックを続けます。最後の行まで手順を繰り返します。

于 2012-04-07T13:08:18.123 に答える