Zählen der Schnittpunkte (Linien) von zwei Mengen von Sequenzen

Question

Ich muss einen Algorithmus finden, der die Gesamtzahl der Schnittpunkte zwischen zwei Sätze von Arrays finden kann, während einer der Array sortiert ist.

Ein Beispiel, wir haben diese beiden Arrays und wir zeichnen Geraden in Richtung entsprechende Zahl.

Diese beiden Arrays gibt uns insgesamt 7 Kreuzungen.

Welche Art von Algorithmen gibt es, um mir bei diesem Problem zu helfen?

Ich habe den Suchknopf verwendet, aber nichts gefunden, das dieses Problem für mich lösen würde. durch einen Vergleich ihrer y Werte

Dank

Answer 1

zwei Zahl M und N gegeben, die Linien wird nicht schneiden, wenn

• der oben M rechts von der Spitze N ist, und die unteren M rechts von der Boden N
• oben M links von der Spitze N ist, und die untere M ist links von der Unterseite N

In den beiden anderen Fällen:

• links oben, rechts unten
• rechts oben, links unten

die Linien tun schneiden.

Im Beispiel ist 8 links von allen 4 Zahlen in der oberen Reihe, und rechts von 3 Zahlen auf der Unterseite, so kreuzt 8 mit drei Zahlen.

5 ist rechts von 8 oben, links von 8 unten, was einen Schnittpunkt ergibt. 5 ist links von 4 und 1 oben und rechts von 4 und 1 unten, was zwei weitere ergibt. Also schneidet 5 drei Zahlen.

Beachten Sie, dass wir den Schnittpunkt von 5 und 8 zweimal gezählt haben. Tatsächlich wird jeder Schnittpunkt zweimal gezählt. Wenn Sie das Beispiel beendet haben, zählen Sie 14 Schnittpunkte. Teilen Sie am Ende um 2, um die Antwort zu erhalten.

Answer 2

können Sie jede Zeile als y=a+bx repräsentieren und dann jede Zeile mit den anderen vergleichen.

Jede Zeile hat maximal einen Schnittpunkt mit jeder anderen Zeile.