私は座標の配列を持っています。つまり、各インデックスに（x、y）座標があります。私は座標のいずれかが単一の行または列にある場合、それを把握したい。課題は、Mが配列の長さである単一のループで行うことです。私は懸命に努力してきましたが、2つのループを使用せずにそれをするようです。アルゴリズムの助けが必要です。Big-ohの座標間の距離Mの
編集：基本的に問題は、N枚のN枚のボードにM枚があることです。各ピースは任意の数だけ垂直方向と水平方向に移動できます。どの作品も他の作品を攻撃できるかどうかを知りたいだけです。
これは、一般的には複雑さ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
基本的に問題は、N個のNボードにM個の部品があることです。各ピースは任意の数だけ垂直方向と水平方向に移動できます。どの作品も他の作品を攻撃できるかどうかを知りたいだけです。 –
すべてが正しいままです。この定義の時間O（M）。限られたボードでは、ハッシュテーブルの代わりに配列を使うほうが簡単です。縦と横の長さがNの配列 - メモリ消費量O（N） – MBo
詳細を教えてください。 –
これは8クイーン問題の一般化ですか？あなたの配列にはクイーンズのボード上の座標のみが含まれています。もしあなたが他のクイーンを攻撃しているなら、その配列を1回通過するといいでしょうか？ – Emmet
実際にはより簡単なバージョン –
だから8ルークの一般化？いずれかの行または列に1より大きい数がある場合、少なくとも2つの部分が互いに攻撃していますか？ – Emmet