Ich wurde mit diesem Problem konfrontiert, und würde gerne einen schnellen Algorithmus haben, um es auszuarbeiten.irgendein eleganter binärer Suchbaumalgorithmus, um das herauszufinden?
Gegeben n Punkte in der 2D Ebene (keiner von ihnen hat einen x Wert oder y Wert gleich einem anderen), ermitteln Sie die Anzahl aller Punktpaare, die eine Linie mit positiver Steigung bilden (zB (0,0)) und (1,1), mit einer positiven Steigung von 45 Grad)
Da das n groß ist (sagen wir 60000), brauche ich einen eleganten Algorithmus, um es innerhalb 1 Sekunde zu halten. Ich weiß, es ist leicht, es mit O (n^2) zu tun, aber es ist einfach zu langsam, was etwa 30 Sekunden dauert. Ist es möglich, einen binären Suchbaum zu haben, um es mit nlogn Komplexität zu tun?
Ich schätze jeden, der mich dazu aufklären möchte.
Das setzt eine gleichmäßige Verteilung voraus. Wenn die Punkte in der Ebene um eine Linie mit negativer Steigung gruppiert sind, dann ist die Zahl viel kleiner als "countOfPairs/2", vielleicht sogar 0. –
Danke für Ihre sofortige Antwort, aber es geht in der Tat um Programmierung, nicht um Mathematik. Ich möchte die genaue Anzahl der Paare kennen, die irgendwelche n Punkte haben, anstatt eine theoretisch durchschnittliche Zahl zu haben. Jeder Algorithmus Vorschlag, der implementiert werden kann? – Daniel
Andrew, soweit ich die Frage verstehe, ist die einzige Zeit, die möglich ist, wenn sie alle perfekt ausgerichtet sind, in diesem Fall, wenn sie in einer positiven Linie ausgerichtet waren, dann würden alle von ihnen positive Linien erstellen, so würde der Durchschnitt Sei immer noch countOfPairs/2. Daniel, kennen wir die Orte dieser Punkte? Es wurde nicht angegeben, also nahm ich an, dass es sich um eine hypothetische Situation handelte. – DanRedux