0

与えられた行列 NxN に対して、0 または 1 のみを持ちます。少なくとも 1 つの 1 が発生する行と列の数を見つけます。

例えば

0 0 0 0

1 0 0 1

1 0 0 1

1 1 0 1

少なくとも 1 回 1 を持つ行数: 3

少なくとも 1 回 1 を含む列数: 3

心は凍りつき、通常の double for ループよりも優れた方法は考えられません。助けを待っている O(n^2) を与えてくれます

4

2 に答える 2

1

この解決策は、O（N ^ 2）未満の行列を読み取ることができないことを証明していますが、この質問の平均が検索で結果を計算したい場合：それはそれを行うか、私がする必要があると言った間の関係ではないと思いますこの問題を O(2*(n^2)) よりも良い順序で解いてください。

配列内のすべてのセルについて知る必要があります。すべての頂点がマトリックス内のセルを指しているグラフがあると仮定します。グラフで検索する必要があるセルの値を見つけるために、最小限のDFSでそれを行うことができます注文。

DFSの時間と空間の分析は、その適用分野によって異なります。理論的なコンピューター サイエンスでは、DFS は通常、グラフ全体をトラバースするために使用され、グラフのサイズに比例して時間 O(|E|) がかかります。これらのアプリケーションでは、最悪の場合、スペース O(|V|) を使用して、現在の検索パス上の頂点のスタックと、既にアクセスした頂点のセットを格納します。したがって、この設定では、時間と空間の境界は幅優先検索の場合と同じであり、これら 2 つのアルゴリズムのどちらを使用するかの選択は、複雑さよりも、2 つのアルゴリズムが生成する頂点順序付けのさまざまなプロパティに依存します。 .

そして、グラフに N^2 個の頂点があります-配列 少なくとも (O(V+E) >= O(V))。したがって、すべてのデータ構造を使用してO（n ^ 2）よりもうまく行うことはできません（この順序の計算はエッジ構造とは関係がないため）。

maxcol=0;
for(int i=0;i<n;i++)
{
  sumcol=0;
  for(int j=0;j<n;j++)
  {
    if (a[i][j]==1)
     {
       sumcol=sumcal+1;
     }  
  }
  if (sumcol>maxcol)
   {
     maxcol=sumcol;
   }
}

行に対してこれを繰り返します。これは非常に簡単な解決策ですが、このコードには最小限のスペースしかありません。アルゴリズムのアイデアで改善することはできません。アルゴリズムの複雑さの意味に注意する必要があります。1 回の検索で解決できますが、複雑さが増すだけです。あなたのコード。

于 2013-03-18T21:05:47.710 に答える
0

アイデア: 行列の各行と列の数値の合計を格納します。

追加のストレージ: O(n * log(n)) - 1 つの数値を格納するために O(log(n)) ビットを想定。

ゼロ以外の行と列をカウントするのに必要な時間: O(n)。

これは時間最適化アルゴリズムであり、「空間と時間最適化アルゴリズム」ではありません。より多くの空間が必要ですが、時間はより少なくて済みます。

于 2013-03-19T00:41:35.753 に答える