0
Angenommen, wir haben zwei Sätze von Punkten, sagen A und B (beide der Größe O(n)) in der Ebene. Können wir in A & B in O(n) Zeit am weitesten Punkte finden?Berechne den weitesten Punkt jedes Punkts
A
Antwort
1
Nein, Sie können nicht den weitesten Punkt für jeden Punkt in O(n) berechnen. Das beste, das Sie erhalten können, ist O(n log n) mit einem 2-d tree. Sie können dies mit einer Technik tun, ähnlich wie das Finden eines nächsten Punktes.
Lesen Sie eine ausführlichere answer here, wo ich ein paar andere Ansätze zeigen, um ein ähnliches Problem zu lösen.
+1
Sie haben das grüne Häkchen, obwohl Sie anscheinend auf das Problem * am nächsten * Paar antworten, nicht auf das * am weitesten * Paar Problem ...? –
+0
@j_random_hacker im Wesentlichen die gleiche coz können Sie den Komparator –
+1
@ willywonka_dailyblah: Vielleicht, das funktioniert für die 2-d-Baum-Lösung, weiß ich nicht, aber es funktioniert definitiv nicht für z. die "Grid" -Lösung in der verknüpften Antwort. Im Allgemeinen, wenn Sie wissen, dass a nahe bei b ist, und dass c nahe bei a ist, dann wissen Sie, dass c zumindest etwas nah an b ist - aber wenn Sie "nahe bei" durch "weit von" ersetzen, dann Schlussfolgerung schlägt fehl. –
Möchten Sie das am weitesten entfernte Punktepaar in A & B finden? Ich schlage vor, dass Sie Ihre Frage neu formulieren und hinzufügen, was Sie bisher getan haben. –
@ Rishit, Danke. Ich habe es geändert. – user2311963
Ich glaube nicht, dass Sie es in O (n) Zeit tun könnten. Aber es ist in O (nlogn) Zeit möglich. –