分治法一维最接近点对java
时间: 2023-11-04 11:00:37 浏览: 56
以下是一维最接近点对的分治法Java实现:
```java
import java.util.*;
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class ClosestPair {
public static double findClosestPair(Point[] points) {
Arrays.sort(points, (p1, p2) -> p1.x - p2.x);
return findClosestPair(points, 0, points.length - 1);
}
private static double findClosestPair(Point[] points, int left, int right) {
if (left >= right) {
return Double.POSITIVE_INFINITY;
}
int mid = left + (right - left) / 2;
double d1 = findClosestPair(points, left, mid);
double d2 = findClosestPair(points, mid + 1, right);
double d = Math.min(d1, d2);
List<Point> strip = new ArrayList<>();
for (int i = left; i <= right; i++) {
if (Math.abs(points[i].x - points[mid].x) < d) {
strip.add(points[i]);
}
}
Collections.sort(strip, (p1, p2) -> p1.y - p2.y);
for (int i = 0; i < strip.size() - 1; i++) {
for (int j = i + 1; j < strip.size() && strip.get(j).y - strip.get(i).y < d; j++) {
double dist = distance(strip.get(i), strip.get(j));
if (dist < d) {
d = dist;
}
}
}
return d;
}
private static double distance(Point p1, Point p2) {
return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}
public static void main(String[] args) {
Point[] points = {new Point(1, 3), new Point(2, 5), new Point(4, 6), new Point(7, 9), new Point(8, 2)};
System.out.println(findClosestPair(points)); // expected output: 1.4142135623730951
}
}
```
在此实现中,我们首先按照点的x坐标进行排序。然后我们使用递归的方式将点对分成两半,分别求出左边和右边的最接近点对距离d1和d2。接下来,我们选取中间位置的点mid,并找出所有x坐标与mid的x坐标相差小于d的点。我们将这些点按照y坐标进行排序,然后在其中查找距离最近的点对。如果找到更小的距离,则更新d。最后,我们返回d作为结果。
时间复杂度:O(nlogn)
空间复杂度:O(n)