[关闭]
@hainingwyx 2017-07-24T03:10:36.000000Z 字数 889 阅读 702

同一直线最大点数问题

数据结构


原题:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.即:给定二维平面中的n点,求过同一直线的点最多的点

分析:
可以通过双重循环遍历。第一层循环遍历不同的点作为主导点,第二层循环遍历剩下的点,考虑其斜率。有几个细节:
1. 统计斜率和点的数量可以用HashMap
2. 需要考虑斜率不存在的情况
3. 需要考虑点重合的情况,同一点不重复计数

  1. import java.util.*;
  2. class Point {
  3. int x;
  4. int y;
  5. Point() { x = 0; y = 0; }
  6. Point(int a, int b) { x = a; y = b; }
  7. }
  8. public class MaxPointsOnOneLine {
  9. public int maxPoints(Point[] points) {
  10. int n = points.length;
  11. if(n < 2) return n;
  12. int ret = 0;
  13. for(int i = 0; i < n; i++) {
  14. // 分别统计与点i重合以及垂直的点的个数
  15. int dup = 1, vtl = 0;
  16. Map<Float, Integer> map = new HashMap<>();
  17. Point a = points[i];
  18. for(int j = 0; j < n; j++) {
  19. if(i == j) continue; //同一个点
  20. Point b = points[j];
  21. if(a.x == b.x) {
  22. if(a.y == b.y) dup++;//重叠的点
  23. else vtl++; //垂直的点
  24. } else { //一般情况,根据斜率划分
  25. float k = (float)(a.y - b.y) / (a.x - b.x);
  26. if(map.get(k) == null) map.put(k, 1);
  27. else map.put(k, map.get(k) + 1);
  28. }
  29. }
  30. int max = vtl; //初始化为垂直的点
  31. for(float k: map.keySet()) {
  32. max = Math.max(max, map.get(k));
  33. }
  34. ret = Math.max(ret, max + dup);//ret需要加上本身的点
  35. }
  36. return ret;
  37. }
  38. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注