二维平面p和q两点间的欧几里得距离公式：
如果对于二维平面上任意多个点，例如：
要找出欧式距离最短的两个点，要如何求解？
- 暴力方式
双重循环： for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { currMin = dist(P[i], P[j]); if (currMin < min) { min = currMin; } } }
- 按某一方向排序，然后化作一维的方式进行比较
import java.util.*; import java.util.List; public class Kata { // 计算欧式距离 public static float dist(Point p1, Point p2) { return (float) Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } public static List<Point> closestPair(List<Point> points) { int left = 0; int right = 0; float min = Float.MAX_VALUE; // 按Y轴方向排序，自定义排序方法； Collections.sort(points, new Comparator<Point>(){ @Override public int compare(Point u1, Point u2) { double diff = u1.y - u2.y; if (diff > 0) { return 1; }else if (diff < 0) { return -1; } return 0; } }); // x轴方向依次比较， //(points.get(j).y - points.get(i).y) < min 确保不会比较的次数太多 for (int i = 0; i < points.size(); ++i) { for (int j = i + 1; j < points.size() && (points.get(j).y - points.get(i).y) < min; ++j) { if (dist(points.get(i), points.get(j)) < min) { min = dist(points.get(i), points.get(j)); left = i; right = j; } } } return Arrays.asList(points.get(left),points.get(right)); } }
虽然看似是O(n^2)的复杂度，但是由于另一个方向的比较次数不会太多，最终的复杂度是比暴力要小很多的。
