いくつかの制約に基づいて行列から値を抽出する

-2

私はNx2行列（Aと呼ぶ）と数Kを持っています。最初の列の値が最大で2番目の列の値は<Kいくつかの制約に基づいて行列から値を抽出する

すなわち最大_i A [i、1] st A（i、2）< K

O（log N）以上の値を抽出する必要があります。これには前処理が含まれていません。つまり、要素を検索する前に行列をソートすることができます。

2016-12-06 yetu

上記の行に何か試しましたか？ – nullpointer

私はまず最初の列に基づいて行列をソートしました。次に、第2の列を横切って、Kより小さい第1の値を探します。しかし、この移動にはO（N）が必要です。任意の前処理の後、行をO（Ng N以上）で検索したい。 – yetu

そして、2番目の列でソートするとどうなるでしょうか？ – MBo

マトリックスを介して第2の列を並び替え行列A

ウォーク、すべてのクエリについてauxillary配列B

に開始されてから現在の行に最大値のインデックスを書き込む - バイナリサーチと最大行imaxを見つけます。行の最初と2番目のセルから値を取得A[B[imax]]

2016-12-07 01:52:35 MBo

答えて