2

配列の 1 つが並べ替えられているのに対し、配列の 2 つのセット間の交差の合計量を見つけることができるアルゴリズムを見つける必要があります。

例として、これら 2 つの配列があり、対応する数値に向かって直線を引きます。 交点

これら 2 つの配列により、合計7 つの交差が得られます。

この問題を解決するために、どのようなアルゴリズムが存在しますか?

検索ボタンを使用しましたが、この問題を解決するものは見つかりませんでした。

ありがとう

4

2 に答える 2

1

2 つの数値 M と N が与えられた場合、線は交差しません。

  • 上の M は上の N の右側にあり、下の M は下の N の右側にあります。
  • 上の M は上の N の左側にあり、下の M は下の N の左側にあります。

他の 2 つの場合:

  • 左上、右下
  • 右上、左下

線は交差します。

この例では、8 は上の行の 4 つの数字すべての左側にあり、下の行の 3 つの数字の右側にあるため、8 は 3 つの数字と交差します。

5 は上の 8 の右側、下の 8 の左側にあり、交点が 1 つになります。5 は 4 の左と上に 1、下に 4 と 1 の右、さらに 2 つです。したがって、5 は 3 つの数と交差します。

5 と 8 の交点を 2 回数えたことに注意してください。実際、すべての交差点は 2 回カウントされます。例を完了すると、14 個の交差を数えることになります。最後に2で割ると答えが出ます。

于 2016-12-11T09:07:18.040 に答える
-1

各行を次のように表し、値y=a+bxを比較して各行を他の行と比較できyます。

各線には、他の線との最大交点が 1 つあります。

于 2016-12-11T08:25:25.693 に答える