8

整数の行列 M が与えられます。行列で 2 つの行が同一かどうかを確認します。最適なアプローチを提供します。

Example:
[{1, 2, 3},
 {3, 4, 5},
 {1, 2, 3}]

上記の行列では、行 1 と行 3 は同一です。

考えられる解決策:

Given a matrix, we can convert each row in a string (example using to_string()
method of C++ and concatenating each element in a row to a string). We do this
for every row of the matrix, and insert it in a table that is something like
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time
for an mxn matrix.

これよりもうまくできますか？または、上記の方法に欠陥がありますか？

4

2 に答える 2

6

あなたの方法は機能しますが、その複雑さには誤りがあります。

最初に、要素がstd::maphas complexO(log(n) * f)にあるかどうかをテストします。ここnで、 はマップ内の要素の数であり、マップにf挿入/検索された 2 つの要素を比較するのに必要な時間の上限です。

あなたの場合、すべての文字列には lengthmがあるため、マップ内の任意の 2 つの要素を比較するとO(m).

したがって、メソッドの全体的な複雑さは次のとおりです。

O(n * log(n) * m)nマップに文字列を挿入します。

ただし、O(n * m)マップではなくハッシュ テーブルを使用すると、(すべてのデータを読み取る必要があるため) 漸近的に最適な期待値まで高速化できます。これは、ハッシュ テーブルO(1)の挿入操作の複雑さが平均的であり、すべての入力文字列のハッシュ関数が 1 回だけ計算されるためです。

そのためにunordered_setC++を使用できます。

于 2013-10-18T12:24:57.600 に答える
0

行列のサイズによっては、すべてを文字列に変換することは、時間とスペースのかなりの無駄のように思えます。

行ごとに一意である可能性が高いハッシュを計算してみませんか。たとえば、すべてのエントリのビット単位の OR を計算し、そのハッシュを行のインデックスと共にマルチマップに保存できます。各行を通過するときに、そのハッシュを計算し、そのハッシュが既に存在するかどうかを確認します。一致する場合は、その行を同じハッシュを持つ他の行と比較して、それらが等しいかどうかを確認します。

これは Big-O よりも複雑ではありませんが、ほぼ確実に定数が小さくなり、使用するスペースも少なくなります。

于 2013-10-21T20:11:23.570 に答える