Big-ohの座標間の距離Mの

私は座標の配列を持っています。つまり、各インデックスに（x、y）座標があります。私は座標のいずれかが単一の行または列にある場合、それを把握したい。課題は、Mが配列の長さである単一のループで行うことです。私は懸命に努力してきましたが、2つのループを使用せずにそれをするようです。アルゴリズムの助けが必要です。Big-ohの座標間の距離Mの

編集：基本的に問題は、N枚のN枚のボードにM枚があることです。各ピースは任意の数だけ垂直方向と水平方向に移動できます。どの作品も他の作品を攻撃できるかどうかを知りたいだけです。

出典

2017-02-02 Hassam Ullah Sheikh

これは8クイーン問題の一般化ですか？あなたの配列にはクイーンズのボード上の座標のみが含まれています。もしあなたが他のクイーンを攻撃しているなら、その配列を1回通過するといいでしょうか？ – Emmet

実際にはより簡単なバージョン –

だから8ルークの一般化？いずれかの行または列に1より大きい数がある場合、少なくとも2つの部分が互いに攻撃していますか？ – Emmet

これは、一般的には複雑さO（MLogm）（ソート）を持つelement distinctness/uniqueness problemです。

何のメモリの制限がない場合は、単一の実行アレイは、問題を解決し

編集を通じて、この場合には、YとX座標のハッシュテーブルを使用することができます。限られたボードの場合、boolean型配列を使用する方が簡単です水平および垂直の長さN。時間複雑度O（M）、メモリ消費量O（N）

for every rook: 
    if Horiz[rook.Y] then 
     two rooks share horizontal 
    if Vert[rook.X] then 
     two rooks share the same vertical 
    Horiz[rook.Y] = True 
    Vert[rook.X] = True

出典

2017-02-02 04:59:34 MBo

基本的に問題は、N個のNボードにM個の部品があることです。各ピースは任意の数だけ垂直方向と水平方向に移動できます。どの作品も他の作品を攻撃できるかどうかを知りたいだけです。 –

すべてが正しいままです。この定義の時間O（M）。限られたボードでは、ハッシュテーブルの代わりに配列を使うほうが簡単です。縦と横の長さがNの配列 - メモリ消費量O（N） – MBo

詳細を教えてください。 –

答えて

関連する問題