1
行列に関する質問があります。要件別行列位置を見つける
セグメントとセグメントのリストがあります。 すべてのセグメントには、名前、開始点または終了点、および開始点と終了点が行列の行または列を参照する場合に記述する値があります。
同じ名前の（ただし、開始点と終了点が異なる）複数のセグメントが存在する可能性があります。
名前のリスト（a、b、c）があります。
位置は、リストの名前を持つすべてのセグメントの範囲（開始点と終了点）に一致するすべての行列位置（x、y）を見つけることです。
これを行うにはどうすればいいですか？
これは、KV-ダイアグラムの論理式の位置を見つけるために必要です。
最初に同じに占有されている行を「圧縮」し、同様に列を圧縮することで、潜在的に多くの時間を短縮できます。これは、すべてのセグメントの垂直方向の端点をソートした後、同じ（水平方向の端点を持つ）列を実行して、最大2m×2mの最大サイズの行列を残すことによって、O（mlog m） mがセグメント数である場合（各名前は多くのセグメントを表すことができるので、アルゴリズムの時間の複雑さにも "m"が必要だと思います）。 –
@j_random_hacker各列と各行に対してこれを行う必要があるので簡単ではありません。間隔にディメンション。セグメントの数は、同じ名前のセグメントが重複していない場合には問題ありません。これは名前ごとに最大のセグメント数を意味しますが、それぞれが1つのセルのみをカバーします。 – maraca
名前が重複していないということは、時間の複雑さには必要ないという意味です。たぶん私はそれを非常にうまく説明しなかったかもしれませんが、同じ列の水平間隔と同じ行の垂直間隔を圧縮すると、本当にrとcを取り除くことができます - 圧縮間隔ごとに、行列の各セルは元の行列の*矩形*に対応します（すべてのセルはアルゴリズムによって同じ数を受け取ります）。 –