0

このようなファイルがあります

A 100 200
A 120 220
B 140 250

別のファイルはこのようなものです

A 130 210
A 133 215
B 180 270

次に、最初のファイルの各行を2番目のファイルの各行と比較し、座標が交差している行を見つける必要があります

出力は次のようになります

A 100 200 A 130 210
A 100 200 A 133 215
A 100 200 A 180 270

そしてそれはそのようになります。

私のコードでは、次のようにコーディングします。最初のファイルから最初の行を取得し、2 番目のファイルのすべての行と比較します。

したがって、これを行うためにツリーのようなデータ構造を実装する方法を知りたいので、複雑さが対数スケールになります。

4

1 に答える 1

3

ツリーのようなデータ構造は必要ありません。ファイルが最初の座標で並べ替えられている場合は、線形時間で簡単に並べ替えることができます。現在関連する行を保持している各ファイルのバッファーを維持するだけで、両方のファイルのバッファーを同期して進める必要があります。重要なのは、他のファイルの特定の線との交差に関連する線は常に互いに隣接しているため、線を破棄すると、それをチェックする必要がなくなることです（ファイルはソート済み）。

于 2012-10-25T01:06:28.410 に答える