9

これは非常に有名な多国籍企業から私に尋ねられた質問です。質問は次のとおりです...

0と1の2DN*N配列を入力します。A（i、j）= 1の場合、i番目の行とj番目の列に対応するすべての値は1になります。すでに1がある場合は、1のままです。

例として、配列がある場合

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

次のように出力を取得する必要があります

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

入力行列はまばらに入力されています。

これはO（N ^ 2）未満で可能ですか？

別の条件で、追加のスペースが提供されていません。スペース<=O（N）を使用して複雑さを実現する方法があるかどうかを知りたいです。

PS：O（N * N）の複雑さを与える答えは必要ありません。これは宿題の問題ではありません。私は多くのことを試みましたが、適切な解決策を得ることができず、ここでいくつかのアイデアを得ることができると思いました。複雑さのために印刷を脇に置いておきます

私の大まかなアイデアは、通過する要素の数を動的に排除して、それらを約2N程度に制限することでした。しかし、私は適切なアイデアを得ることができませんでした。

4

13 に答える 13

8

最悪の場合、出力を生成するためにN*N-Nビットを0から1に切り替える必要がある場合があります。あなたはO（N * N）でかなりうまく立ち往生しているように思われるでしょう。

于 2010-09-07T14:31:00.990 に答える
6

最良の場合に最適化できると思いますが、最悪の場合はまだO（N * N）であると言いたくなります。最悪の場合はすべて0の配列になり、調べる必要があります。すべての要素。

最適化には、「1」が見つかったらすぐに行または列をスキップすることが含まれます（詳細は提供できますが、O（N * N）は気にしないと言っていましたが、メタデータがない限り、行/列全体が空であるか、複数のフィールドを一度にチェックするSIMDスタイルの方法がない場合（たとえば、すべての行が4で整列され、32ビット相当のデータを読み取ることができる場合、またはデータが次の形式である場合）ビットマスク）、常にゼロ配列の問題に対処する必要があります。

于 2010-09-07T14:31:09.370 に答える
6

明らかに、出力行列もその否定バージョンもスパースである必要はありません（最初の行の半分が1に設定され、その他は0に設定された行列を取得してください）。したがって、時間は出力に使用できる形式によって異なります。 。（入力は要素のリストまたは同等のものであると想定しています。そうしないと、マトリックスがスパースであることを利用できなかったためです。）

O（M + N）空間と時間の簡単な解決策（Mは入力行列内の1の数）：1で満たされた長さNの2つの配列を取得し、入力内のすべての配列を反復処理し、各ドロップに対してX最初の配列からの座標と2番目の配列からのY。出力は2つの配列であり、結果の行列を明確に定義します。最初の配列のX座標と2番目の配列のY座標が0の場合、その（X、Y）座標は0です。

更新：言語によっては、同じ行を複数回参照することで、いくつかのトリックを使用して通常の2D配列を返すことができます。たとえば、PHPの場合：

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

もちろん、これは、書き込もうとしない限り、通常の配列です。

于 2010-09-07T15:21:44.077 に答える
3

行列のすべてのエントリをチェックする必要があるため、最悪の場合は常にN*Nになります。

小さな2*Nの追加ストレージを使用すると、O（N * N）で操作を実行できます。行ごとにマスクを作成し、列ごとに別のマスクを作成するだけです。配列をスキャンして、必要に応じてマスクを更新します。次に、もう一度スキャンして、マスクに基づいて結果マトリックスにデータを入力します。

入力行列が変化している場所で何かをしている場合は、（単純なマスクではなく）入力の各行と列のゼロ以外のエントリの数を格納できます。次に、入力のエントリが変更されたら、それに応じてカウントを更新します。その時点で、出力マトリックスを完全に削除し、出力マトリックスを維持するのではなく、マスク/カウントを直接クエリします（本当に維持したい場合は、N N時間未満で変更されたときに更新することもできます）。したがって、初期マトリックスのロードはO（N N）のままですが、更新ははるかに少なくなる可能性があります。

于 2010-09-07T14:47:49.750 に答える
3

入力行列はスパースである可能性がありますが、スパース形式（つまり、最初に設定されたペアのリスト）で取得できない限り(i,j)、入力を読み取るだけでΩ（n ^ 2）時間が消費されます。入力がまばらであっても、書き込みにO（n ^ 2）出力が発生するのは簡単です。チートとして、設定された行と設定された列のリストを出力することを許可された場合、線形時間に到達する可能性があります。アルゴリズムが実際に「はい」または「いいえ」よりも実質的な結果を生成する必要がある場合、魔法はありません。

別の回答に対するMcdowellaのコメントは、別の代替入力形式であるランレングスエンコーディングを示唆しています。スパース入力の場合、それを読み取るのに明らかにO（n）時間しか必要ありません（0と1の間にいくつの遷移があるかを考慮してください）。しかし、そこから故障します。次のように構成された入力行列について考えてみます。

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

つまり、最初の行で0と1を交互に表示し、それ以外の場合は0を交互に表示します。n/2全部で1つあるので、明らかにまばらです。ただし、RLE出力はすべての行でこのパターンを繰り返す必要があり、O（n ^ 2）出力になります。

于 2010-09-07T14:55:29.950 に答える
2

あなたは言う：

次のように出力を取得する必要があります...

したがって、N^2要素を持つ行列全体を出力する必要があります。これはO（N * N）です。

問題自体はO（N * N）ではありません。行列全体を計算して保存する必要はありません。必要なのは、それぞれサイズNの2つのベクトルLとCだけです。

L [x]は、行xが1の行の場合は1、それ以外の場合は0です。

行xが1の行の場合、C [x]は1であり、それ以外の場合は0です。

初期行列はスパースであるため、これらのベクトルはO（N）で作成できます。入力データは行列ではなく、ゼロ以外の各要素の座標（行、列）を含むリストになります。このリストを読みながら、L [line]=1およびC[column]= 1に設定すると、問題は解決されます。L[l]==1またはC[c]=の場合、M [l、c] ==1 = 1

于 2010-09-07T15:03:51.767 に答える
2

こんにちはみんな、

mb14からのコメントのおかげで、O（N N）時間以内に解決できると思います...最悪の場合はO（N N）...

実際には、与えられた配列は

  1 0 0 0 1
  0 1 0 0 0 
  0 1 1 0 0 
  1 1 1 0 1
  0 0 0 0 0

サイズNの2つの配列を作成しましょう（これは最悪の場合です）...1つは行と他の列のインデックス作成専用です...a [i] [1]=0の配列を1つの配列に入れてからa[1 ] [j]=0別の。

次に、これらの値のみを取得し、2番目の行と列を確認します...このようにして、0のみの行と列の値を取得します;完全に...

行配列の値の数は結果配列の0の数を示し、ポイントa[行配列値][列配列値]はそれらのポイントを示します...。

O（N N）以下でそれを解くことができ、最悪の場合はO（N N）です...ご覧のとおり、（サイズNの）配列は減少します...。

私はいくつかのアレイに対してこれを行い、それらすべての結果を得ました... :)

私がどこか間違っているなら私を訂正してください...

コメントをありがとうございました...皆さんはとても親切で、途中でかなりのことを学びました... :)

于 2010-09-08T14:08:29.450 に答える
1

やるべきことは明らかにありO(N^2)ます。マトリックス内

1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

すべてのビットを1に設定する必要があり、1に設定する必要N*(N-1)はありません（この5x5の場合は20）。

逆に、常に時間内にそれを実行するアルゴリズムを思い付くことができますO(N^2)。一番上の行に沿って合計し、列を許可し、行または列がゼロ以外の答えを取得した場合は、行または列全体に入力します。次に、小さい方の（N-1）x（N-1）問題を解決します。

したがって、少なくとも取らなければならないケースが存在し、どのようなケースでも余分なスペースなしN^2で解決できます。N^2

于 2010-09-07T14:39:06.457 に答える
0

行列がスパースである場合、複雑さは入力エンコーディングに大きく依存し、特にNN 2などでは十分に測定されませんが、Nに関しては、入力の複雑さMinと出力の複雑さMoutです 。O（N + M in + M out）のようなものを期待しますが、エンコーディングとそれで遊ぶことができるトリックに大きく依存します。

于 2010-09-07T14:55:38.310 に答える
0

これは、入力データ構造に完全に依存します。行列（1と0）を2D配列として渡す場合は、それをトラバースする必要があります。これがO（N ^ 2）です。ただし、データがスパースであるため、入力として1のみを渡す場合は、出力がO（M）になるようにすることができます。ここで、Mはセルの数ではなく、1セルの数です。これは次のようなものになります（以下の擬似コード）：

リストf（リストl）{
   リストrows_1;
   リストcols_1;

    l{の各要素に対して
        rows_1 [elem.row] = 1;
        cols_1 [elem.col] = 1;
    }

    結果を一覧表示します。
    rows_1の各行に対して{
        cols_1の各列について{
             if（row == 1 || col == 1）{
                 add（result、new_elem（row、col））;
             }
        }
    }
   結果を返します。
}
于 2010-09-07T15:01:55.517 に答える
0

値をチェックするときは、マトリックスの中心を埋めないでください。要素を調べながら、1がある場合は、最初の行と最初の列に対応する要素を設定します。その後、戻って記入し、横切ってください。

編集：実際には、これはアンディのものと同じです。

于 2010-09-07T15:11:31.123 に答える
0

データ構造によって異なります。

行の考えられるケースは2つだけです。

  • 入力に要素（i、_）がある場合、行iは1で埋められます
  • 他のすべての行は同じです。つまり、入力に要素（_、j）がある場合、j番目の要素は1です。

したがって、結果は行への参照の配列としてコンパクトに表すことができます。必要な行は2つだけなので、結果はO（N）メモリのみを消費します。例として、これは次のようにPythonで実装できます。

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

サンプル呼び出しは次のようになります

 f([(1,1),(2,2),(4,3)],5)

結果で

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

重要な点は、配列がここにコピーされないことです。つまり、M [row]=Aは単なる参照の割り当てです。したがって、複雑さはO（N + M）です。ここで、Mは入力の長さです。

于 2010-09-08T11:26:23.983 に答える
0 
#include<stdio.h>

含む

int main（）{int arr [5] [5] = {{1,0,0,0,0}、{0,1,1,0,0}、{0,0,0,0,0} 、{1,0,0,1,0}、{0,0,0,0,0}}; int var1 = 0、var2 = 0、i、j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

このプログラムは24個の一時変数（var1、var2、i、j）のみを使用するため、時間計算量O（n ^ 2）の定数空間で実行されます。<でこの問題を解決することはまったく不可能だと思います。 O（n ^ 2）。

于 2010-09-27T16:28:23.423 に答える